Подскажите что-то что бы конкретно разобраться в CRC

понятным языком про такие алгебраические структуры как поля

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers.

То есть, что бы определить поле, нужно множество значений и операции + - * /, которые ведут себя примерно так же как и с обычными числами. Всё. Больше ничего. Но дальше начинаются нюансы, поле может быть конечным, целочисленным, не все наборы операций полезны для математиков (= не все решают какую-то задачу).

А, ну вот, я открыл русскую википедию, там переводная заумь, чтобы никто ничего не понял, начинающаяся с Галуа и полей. Почитай английскую, там более человечно написано.

Сами полиномы выбираются тщательным математическим анализом. В упрощённом виде это брутфорс по случайным данным, добавление случайных пакетов помех, и измерение в скольки процентах случаев код сработал правильно.

какие еще аналоги есть

https://en.wikipedia.org/wiki/Error_detection_and_correction#Types_of_error_detection

Я полностью сам разобрался только с кодом Хэмминга, который по сути многобитный паритет. В случае ошибки в битах паритета получается как бы адрес ошибочного бита, и его можно даже исправить. А адрес получается потому что каждый бит паритета считается по сеткам 101010.. 11001100.. 1111000011110000..

… конкретно разобраться в CRC

чтобы что?

ты хочешь сам их разрабатывать?

https://www.sunshine2k.de/articles/coding/crc/understanding_crc.html

Там много ссылок в конце, в частности http://www.ross.net/crc/crcpaper.html:

A Painless Guide to CRC Error Detection Algorithms

Скачать: http://www.ross.net/crc/download/crc_v3.txt.

чтобы что?

Чтобы посчитать контрольную сумму «Эзернет»-пакета? Если значение этой контрольной суммы не отображается в «Вайршарке», то это не означает, что ее нет.

Уверен, что есть готовая утилитка для этого. Не надо забивать голову полями Галуа.

Надо сделать скидку на ник всё же

надо самому писать, реализацию отличную от википедии, для образовательных целей

Питерсон, Уэлдон, «Коды, исправляющие ошибки». Это понятная «методичка», понятнее я не встречал, там есть вся база начиная с необходимой алгебры (группы, кольца, поля) и особо ничего лишнего. Дальше читай стандарты, статьи в журналах типа IEEE и т.п.

Ок, начну. Спасибо

Что значит отличную от википедии? Со своим полиномом или что?

Да, со своими полиномом и надо под mips все это еще оптимизировать на ассемблере под этот SoC

Помнится, к первому изданию Hacker’s Delight Уоррена выходила бесплатная доп. глава про CRC, но во второе издание не вошла. Не знаю, можно ли где-то её щас найти.

Да, со своими полиномом и надо под mips все это еще оптимизировать на ассемблере под этот SoC

зачетная «норкомания»!

А если серьезно, то твоя задача распадается на 3 совершенно независимые:

• Реализация алгоритма на произвольном полиноме
• Оптимизация этого алгоритма на целевой платформе
• Выбор полинома удовлетворяющего заданным требованиям (выявление определенного количества ошибок на указанном размере и т.д.)

И если первая задача выполнима для любого погромиста. Вторая для квалифицированного. То третья это задача матерого математика. Потому как выбор полинома далеко не случайный и там много унылого матана.

С учетом того, что ты хочешь все это реализовать в одно лицо, ты очень честолюбивый.

Я бы взял какой-нибудь условный талмуд по теме помехоустойчивого кодирования, чтобы там несколько изданий было, и читал бы, заглядывая в отдельную книгу по теорию матаппарата только тогда, когда надо непосредственно что-то выяснить, а из первой книги не понятно.

Если просто читать про группы и проч. абстрактную алгебру per se, можно в ней утонуть, забыв про crc и всё на свете. Стоит ли оно того?

Написание реализации может дать знание только о самой реализации, и ноль знаний о теории. Вообще, написание собственной реализации в 90% не даёт ничего нового, пустая трата времени в плане образования.

Если не получится то и хрен с ним, больше хотелось бы на ассемблере под мипс поработать, вот думал какой алгоритм реализовать ну и решил CRC, а что бы хоть ТОЛК был решил поглубже разораться, но вот что-то уже понимаю, что не осилю. Если это действительно так не просто, меня немного расстраивает тот факт, что часто мы используем какие-то алгоритмы, не представляя их глубины. CRC то понятно, это практически везде, но что если ошибка на линии связи например практически маловероятна например 1 на 10 в минус 12 степени, тот тут и просто хватит подсчитать кол-во четных байт.

Начать с теории групп.

но что если ошибка на линии связи например практически маловероятна например 1 на 10 в минус 12 степени

это сфероконина в вакууме. для случаев когда линия связи проходит внутри кристалла либо между отдельными чипами по идеально спроектированной плате. В остальных случаях везде проверка црц, хемминги и прочии риды-соломоны.

Если задача просто прогать на асм под мипс, то бери стандартный алгоритм и фигач. С учетом эталонных реализаций всегда сможешь себя проверить.

Для программирования матаппарат GF не нужен.

Там всего пара вариантов. Либо в лоб складывать сдвигать все биты. Либо по таблице (но это только для crc8, зато супербыстро).

Никакие поля Галуа для CRC не нужны. Я так и не понял почему про них везде пишут когда объясняют CRC, это только запутывает и никакой практической пользы не даёт. На самом деле CRC это вот:

1) инициализируем состояние (оно не обязано быть 32-битным, если что) всеми единицами

2) подаём из входных данных по одному биту, и на каждый входной бит делаем следующее:

2а) XOR-им самый младший бит (нулевой) состояния с входным битом данных

2б) сдвигаем состояние цикически вправо на 1 бит (то есть 3-й его бит становитя вторым, 2-й первым, 1-й нулевым, нулевой последним итд)

2в) если последний бит (он раньше был первым и мы его уже по-xor-или с битом данных) равен единице, то xor-им всё состояние с некоей константой

3) в самом конце обычно инвертируют то что получилось (это чтобы из нулевых входных данным получилось нулевой crc в не все единицы)

Либо по таблице (но это только для crc8, зато супербыстро).

Почему только crc8? crc32 тоже все по таблице считают.

https://habr.com/ru/articles/770014/ тут разжевано

Если самому придумывать что-то полноценное и серьёзное, тогда придётся учить много матана. Больше, чем даётся у условных прикладных математиков, включая магистров (неучи со специалитетом и бакалавры вообще рядом не стоят по необходимому количеству матана). А вот какие-нибудь классические академические математики должны этот матан учить, правда ценой других дисциплин.

Если просто реализовать на абы как, то хватит осознанного гугления и вопросов к чат гопоте.

Я бы сказал, что первое и второе ерунда. Первое фигня даже для математика, который очень плохо кодит, второе, вполне выполнимо для человека с инженерными навыками при наличии времени. Большой опыт конечно очень значительно ускорит процесс, но если времени и желания много, то даже обычный математик справится, хотя будет тяжело очень. Но третий пункт он очень неприятен даже для математиков. Во-первых, не каждый математик знает хорошо именно эту область математики, во-вторых, это уже уровень КФМН. Точнее я знаю ИРЛ КФМН которые либо не возьмутся за это, либо не осилят и не знаю никого ниже КФМН по знанию математики, кто мог бы осилить (в смысле бывают люди без бумажек в матане, но любой кто с такой задачкой справится при желании мог бы получить КФМН ИМХО, т.к. в каком-то смысле это даже проще, там ты не так жестко ограничен областью математики, можно брать то что роднее).

Научись отличать реализацию чего-то что умные дяди придумали до тебя от придумывания чего-то умными дядями. Если ты думаешь, что приведённый алгоритм (я его даже не проверял, но поверю на слово что он рабочий, оставим его на твоей совести, вроде что-то подобное я когда-то читал) единственный и идеальный для задачи корректирования ошибок, то я спешу тебя разочаровать. Таких алгоритмов можно придумать много и по некоторым качествам они могут быть сильно лучше этого. Но вот чтоб придумать новый алгоритм, а не взять готовый из учебника/интернета/головы умного дяди, нужны как раз те самые поля галуа, теория вероятностей и куча разной векторной математики, которая даже может будет пересекаться с физикой, точнее математикой которую придумали физики для решения своих, физических задач.

единственный и идеальный для задачи корректирования ошибок, то я спешу тебя разочаровать.

Разумеется, не единственный. Но автор спросил про CRC (читай тему то), а он делается именно так. Новый алгоритм он не спрашивал.

Да, со своими полиномом и надо под mips все это еще оптимизировать на ассемблере под этот SoC

Ну я даже не знаю. CRC это целое семейство алгоритмов. Ты бы в википедии на разные полиномы посмотрел в статье про CRC. ТС хочет свой придумать. А это, мягко говоря, сложно.

Ты бы почитал мой ответ что ли, там конкретная константа не указана, как и битность. А больше они ничем не отличаются.

А это, мягко говоря, сложно.

Сомневаюсь. Почти уверен, что если перейти от теоретического матана к анализу фактического алгоритма в виде xor-а с константой (безо всяких полиномов) то всё станет намного проще. А представление в виде полиномов там исторически сложилось.

CRC то понятно, это практически везде, но что если ошибка на линии связи например практически маловероятна например 1 на 10 в минус 12 степени, тот тут и просто хватит подсчитать кол-во четных байт.

Если совместимость подсчёта контрольной суммы с другими устройствами не имеет значения, тогда зачем только подсчитывать контрольную сумму данных? Если уж вносить избыточность по данным, тогда гораздо лучше после подсчёта контрольной суммы сразу исправлять ошибку, если она возникнет при передаче данных, а не просто выявлять ошибку и всё, как это делает CRC.

Главное отличать - то ли там в полезных данных один бит исказился, то ли рандомный мусор пришел в котором ничего исправлять не надо.

Главное отличать - то ли там в полезных данных один бит исказился, то ли рандомный мусор пришел в котором ничего исправлять не надо.

И каким образом ты поймёшь один или все разряды данных испорчены по неверной контрольной сумме?

Желание знать что то - похвальное. Вот я делал CRC и программные и аппаратные, я понимаю как они работают и даже знаю как их сделать самому, в том числе рандомайзеры-скремблеры. Но всегда беру готовые решения или конфигураторы

(в том числе для Ethernet FCS сам считал)

Если хочется сломать себе голову и многое узнать, то можно обратить внимание на коды LDPC. У меня бошка кипела пока я постигал LDPC и «какие то там поля Галуа»

если я не собираюсь исправлять бит - тогда мне без разницы, один там бит испорчен или все, просто отбрасываем посылку. А вот если, как ты предлагаешь, использовать самокорректирующийся код - тогда важно.

Например, LDPC позволяет увидеть какие именно биты повреждены и с какой достоверностью их следует изменить. И все равно, как правило, совместно с LDPC применяют и тупо CRC, если после всех исправлений CRC битое то уже всё, хотя в радиосвязи есть методики досылки битов избыточности для повторных попыток декода чтобы сойтись в CRC