Комментарии 43
А почему вы Галуа называете Гаула ?
Еще суровее — он Гаул.
Это как Саул, только Гаул. :)
Это как Саул, только Гаул. :)
Ёлки, я даже полез в Гугл гуглить, неужели всю жизнь я называл тов. Галуа неправильно. Оказалось, правильно. Поставьте плюс те, кто сделал так же. :)
Гаул, наверное, его незаконнорожденный брат. Великий Гаул положил поле в баул.
В первый раз, когда разбирался с темой, я прочитал «поле ГаУла». Так и запомнил. Так и изложил. Не иеемт занчнеия, в каком порядке располоежны буквы, блин.
С таблицами степеней и логарифмов гораздо проще выходит, а произвольная размерность поля на практике нигде не нужна.
Лет 15 назад мне тоже потребовалось восстановить полученные в alma matr знания (совсем давно дело было), нашёл у себя в архиве (GF2^16):
Лет 15 назад мне тоже потребовалось восстановить полученные в alma matr знания (совсем давно дело было), нашёл у себя в архиве (GF2^16):
uint16_t gfpow2[65536];
uint16_t gflog2[65536];
// генерируем таблицы
void gentables()
{
gfpow2[0]=1;
gfpow2[1]=2;
gflog2[1]=0;
gflog2[2]=1;
for(int i=2; i<0xFFFFu; i++)
{
gfpow2[i] = mul2(gfpow2[i-1]);
gflog2[gfpow2[i]]=i;
}
gfpow2[0xFFFFu]=1;
}
static inline const uint16_t log2(uint16_t a)
{
assert(a != 0);
return gflog2[a];
}
// умножение
static inline const uint16_t gfmul(const uint16_t a, const uint16_t b)
{
if(a == 0 || b == 0)
return 0;
register int64_t tmp = gflog2[a] + gflog2[b];
return gfpow2[ uint16_t((tmp > 0xFFFFu) ? tmp - 0xFFFFu : tmp) ];
}
// деление
static inline const uint16_t gfdiv(const uint16_t a, const uint16_t b)
{
assert( b != 0 );
if( a == 0 ) return 0;
register int64_t tmp = gflog2[a] - gflog2[b];
return gfpow2[ (tmp < 0 ) ? 0xFFFFu+tmp : tmp ];
}
// получаем q-значение
static inline const uint16_t QParity(uint16_t* stream, uint16_t n /* max words in stream <64k*/)
{
assert( n <= 65534 && n > 0);
uint16_t Qx=gfmul(gfpow2[0],stream[0]);
for(size_t k=1; k<n; k++)
{
if(stream[k] != 0)
{
Qx^=gfmul(gfpow2[k],stream[k]);
}
else
{
Qx^=0;
}
}
return Qx;
}
// восстановление по q-значению
static inline const uint16_t recoverDxByQ(uint16_t* stream, uint16_t dx /* индекс битого слова*/, uint16_t Q, uint16_t Qx)
{
return gfmul(stream[Q]^Qx,gfpow2[0xFFFFu-dx]);
}
Всё верно. Через логарифмы много проще. Только вот не удалось мне найти таблицы степеней для GF[256].
Таблицу степеней 2 построить просто: каждый раз умножаем на 2 (как обычно, сдвиг влево на 1 разряд), и если результат >= 256 делаем xor с порождающим полиномом.
Так это-же очевидно:
uint16_t gfpow2[0xFF];
uint16_t gflog2[0xFF];
// генерируем таблицы
void gentables()
{
gfpow2[0]=1;
gfpow2[1]=2;
gflog2[1]=0;
gflog2[2]=1;
for(int i=2; i<0xFF; i++)
{
gfpow2[i] = mul2(gfpow2[i-1]);
gflog2[gfpow2[i]]=i;
}
gfpow2[0xFFu]=1;
}
Спасибо за статью, отличная тема! Наконец-то доходчивое объяснение сути полей Галуа.
Касательно надёжности радиосвязи: не кодированием единым она достигается. Какие ещё меры вы собираетесь реализовывать? Какие методы модуляции?
Касательно надёжности радиосвязи: не кодированием единым она достигается. Какие ещё меры вы собираетесь реализовывать? Какие методы модуляции?
Проверять работу кодироваия буду на микросхеме LT8920 – интегрированный приёмо-передатчик с интерфейсом SPI. Модуляция у него GFSK на 2,4 ГГц. Там даже встроенная проверка CRC есть, и реализовано кивитирование. Просто захотелось иметь в коллекции самописных C++ библиотек собственную реализацию кодирования Рида-Соломона. Интересно разобраться.
Просто захотелось иметь в коллекции самописных C++ библиотек собственную реализацию кодирования Рида-Соломона. Интересно разобраться.
Когда-то давно сам разбирался с этим. Для микроконтроллеров понял, что обобщенные варианты достаточно сложны и не приносят пользы, за исключением возможности варьировать параметры. Поэтому я сделал модель, выбрал нужные параметры кодера, зафиксировал их, а потом сделал реализацию со сквозной оптимизацией кодека типа (15,11) в поле GF(256). Правда в моем случае декодер работал на более мощной железке, но зато кодеру не нужно было почти ничего: для ускорения можно было использовать 8 таблиц по 16 байт, но если памяти не хватало — можно было вычислять всё вообще без использования каких-либо таблиц, но чуть медленнее. Вся схема чудесно трудилась кажется на MSP430C1132 (не помню точно номер за давностью лет), где было всего-то 128 байт памяти.
Какое-то сложное получилось обобщенное умножение, есть же варианты проще. И через таблицы степеней/логарифмов и через композитные поля и через разделение на группы битов. И все это хорошо ложится на микроконтроллеры, а композитные поля еще полезны при реализации в железе.
Прямо хоть самому статью написать про это. Только не знаю, будет ли интересно кому-нибудь? Ведь вроде же вся информация и так есть в разнообразных научных статьях.
Прямо хоть самому статью написать про это. Только не знаю, будет ли интересно кому-нибудь? Ведь вроде же вся информация и так есть в разнообразных научных статьях.
Есть ли у вас модель помех используемого радиоканала? Под ней понимаются не только характерные для имеющейся аппаратуры искажения сигнала, но и эфирные помехи в той местности, где аппаратура будет работать.
Иначе ваше шумоподавление будет хорошо работать за городом, где радиошума мало (и шумоподавление в общем то не очень нужно), но будет плохо работать в городе (где много источников помех).
Иначе ваше шумоподавление будет хорошо работать за городом, где радиошума мало (и шумоподавление в общем то не очень нужно), но будет плохо работать в городе (где много источников помех).
Нет. Радиоканал — «на аутсорсе». Им занимается копеешный интегрированный приёмо-передатчик. С моей стороны SPI только и цифры.
Какой чип вы используете?
Что вы посылаете в передатчик, и что приходит из приемника?
Дело в том, что полезные данные (payload) уходят в эфир в обрамлении дополнительной информации (overhead).
Состав посылки:
1) Преамбула. Обычно используется меандр (1010101010101.....). Он нужен для настройки АПЧ для ЧМ приемника. Если у вас канал АМ — преамбула не обязательна.
2) Синхропосылка (иногда называется маркер). По синхропосылке приемник выставляет битовую и байтовую синхронизацию. Длина синхропосылки примерно от 8 до 32 бит, ее содержимое не случайно — оно должно иметь хорошую автокорреляцию само с собой. Важный для вас момент — где то (в микросхеме?) определяется допустимое количество ошибок в синхропосылке, которое определяет и допустимое соотношение сигнал/шум, выше которого вы прыгнуть не сможете.
Синхропосылка должна быть сбалансирована по количеству 0/1, поскольку сразу после определения её наличия ЧМ приемник фиксирует АПЧ, и до конца всей посылки частота приема не изменяется. Это позволяет дальше передавать любые несбалансированные данные.
АПЧ можно не отключать, если данные передаются кодом «Манчестер», но вы за это заплатите удвоением времени передачи.
3) Собственно полезные данные. Если длина посылки переменная, то перед данными должен идти байт длины посылки (как в строках в Паскале). Если длина посылки постоянная, эту длину надо объяснить микросхеме как в приемнике, так и в передатчике.
Надо посмотреть по даташиту на микросхему, что произойдет при искажении байта длины посылки. Обычно ничего хорошего, поскольку приемник будет ожидать контрольную сумму в другом месте, и выключится либо раньше чем нужно, либо позже.
4) Контрольная сумма, от 8 до 32 бит.
И вот тут вопрос — выдаст ли приемник вам посылку, если контрольная сумма будет неверная? Если нет — у вас нет возможности осуществлять шумоподавление в принципе.
В результате обычно получается, что вам нужно осуществлять «закат солнца вручную». То есть переводить приемник в прозрачный режим, когда он высыпает из себя всё, что принимает из эфира, и вручную разбирать посылку с шумоподавлением. Не забывая вовремя управлять аппаратной частью (включать/отключать АПЧ).
Без модели помех вы скорее всего получите хорошее подавление случайных помех (искажение N бит на длине M), на которые и рассчитаны стандартные алгоритмы (при превышении N исправления данных не будет). В то же время промышленные помехи выглядят иначе — они как раз выбивают относительно большое количество бит подряд (надо набрать статистику примерно за неделю, чтобы понять сколько именно у вас в эфире). Против этого используют скремблирование — перемешивание байт при передаче (после добавления избыточности) с обратным процессом на приемнике (до шумоподавления). При этом длинная помеха «размешивается» по длине, что позволяет осуществить шумоподавление.
Что вы посылаете в передатчик, и что приходит из приемника?
Дело в том, что полезные данные (payload) уходят в эфир в обрамлении дополнительной информации (overhead).
Состав посылки:
1) Преамбула. Обычно используется меандр (1010101010101.....). Он нужен для настройки АПЧ для ЧМ приемника. Если у вас канал АМ — преамбула не обязательна.
2) Синхропосылка (иногда называется маркер). По синхропосылке приемник выставляет битовую и байтовую синхронизацию. Длина синхропосылки примерно от 8 до 32 бит, ее содержимое не случайно — оно должно иметь хорошую автокорреляцию само с собой. Важный для вас момент — где то (в микросхеме?) определяется допустимое количество ошибок в синхропосылке, которое определяет и допустимое соотношение сигнал/шум, выше которого вы прыгнуть не сможете.
Синхропосылка должна быть сбалансирована по количеству 0/1, поскольку сразу после определения её наличия ЧМ приемник фиксирует АПЧ, и до конца всей посылки частота приема не изменяется. Это позволяет дальше передавать любые несбалансированные данные.
АПЧ можно не отключать, если данные передаются кодом «Манчестер», но вы за это заплатите удвоением времени передачи.
3) Собственно полезные данные. Если длина посылки переменная, то перед данными должен идти байт длины посылки (как в строках в Паскале). Если длина посылки постоянная, эту длину надо объяснить микросхеме как в приемнике, так и в передатчике.
Надо посмотреть по даташиту на микросхему, что произойдет при искажении байта длины посылки. Обычно ничего хорошего, поскольку приемник будет ожидать контрольную сумму в другом месте, и выключится либо раньше чем нужно, либо позже.
4) Контрольная сумма, от 8 до 32 бит.
И вот тут вопрос — выдаст ли приемник вам посылку, если контрольная сумма будет неверная? Если нет — у вас нет возможности осуществлять шумоподавление в принципе.
В результате обычно получается, что вам нужно осуществлять «закат солнца вручную». То есть переводить приемник в прозрачный режим, когда он высыпает из себя всё, что принимает из эфира, и вручную разбирать посылку с шумоподавлением. Не забывая вовремя управлять аппаратной частью (включать/отключать АПЧ).
Без модели помех вы скорее всего получите хорошее подавление случайных помех (искажение N бит на длине M), на которые и рассчитаны стандартные алгоритмы (при превышении N исправления данных не будет). В то же время промышленные помехи выглядят иначе — они как раз выбивают относительно большое количество бит подряд (надо набрать статистику примерно за неделю, чтобы понять сколько именно у вас в эфире). Против этого используют скремблирование — перемешивание байт при передаче (после добавления избыточности) с обратным процессом на приемнике (до шумоподавления). При этом длинная помеха «размешивается» по длине, что позволяет осуществить шумоподавление.
И вот тут вопрос — выдаст ли приемник вам посылку, если контрольная сумма будет неверная? Если нет — у вас нет возможности осуществлять шумоподавление в принципе.Приёмопередатчик LT8920. В случае битых данных, он выдаёт посылку, и выставляет бит CRC err. Так что не придётся «закатывать вручную». А про скремблирование — сам думаю. Дополнить Рида-Соломона скремблером. Так, вроде, в CD дисках сделано. Их можно царапать широкими царапинами.
Обратите внимание на случай искажения байта длины посылки. Это очень критичное для шумоподавления место. Возможно будет проще переключиться на режим с фиксированной длиной и передавать длинные данные в несколько пакетов.
Согласен. Собственно даже без «шумоподавления» я предпочитаю фиксированную длину одной посылки. Вообще помехоустойчивое кодирование с восстановлением данных тоже гарантией мне не кажется. И лучше всего — это квитирование каждой посылки с автоповтором, в случае отсутствия ответа. Но это не значит, что не нужно для себя изучить помехоустойчивое кодирование. Вдруг придётся передавать на расстояния, на которых квитанция будет идти несколько минут.
Наличие квитирования зависит от задачи. Вы можете передавать команду или разовые события которые пропустить нельзя. А можете передавать состояние объекта с медленно изменяющимися данными — и в этом случае пропуски не важны, следующая передача доставит нужные данные.
Изучение — это правильно. В свое время я даже патент получил на новый способ помехоустойчивого кодирования :).
Изучение — это правильно. В свое время я даже патент получил на новый способ помехоустойчивого кодирования :).
У этого чипа есть встроенная возможность исправления ошибок — FEC13 и FEC23, без подробного описания, что это такое.
На CD дублирование. И широкая царапина — просто чтение из соседнего сектора без царапины (ну примерно)
Нет на CD дублирования, там размазывание данных. Т.е. при ошибке чтения одного сектора ошибка «размазывается» по части данных из нескольких соседних секторов — а поскольку они защищены кодами Рида-Соломона, восстановить их не проблема. В результате даже при ошибке чтения нескольких подряд идущих секторов данные еще можно восстановить (если я правильно помню, длина царапины при этом может достигать нескольких миллиметров).
АПЧ можно не отключать, если данные передаются кодом «Манчестер», но вы за это заплатите удвоением времени передачи.
Не манчестером единым. Есть и более эффективные сбалансированные коды, например, 8b/10b. Время передачи увеличивается всего на 12,5%, а не вдвое, как у «Манчестера». Я даже реализовал этот метод для записи сигналов на магнитофон ZX-Spectrum. Заработало. Правда, помехоустойчивость оказалась хуже, чем у оригинального кода «FM», т.е. передача нуля последовательностью 10, а единицы — 1100.
До сих пор не понимаю, как это произошло. Но факт. «Манчестер» тоже испытывали, он показал близкую к 8b/10b и недостаточную эффективность. Ещё я моделирование проводил, внося в сигнал преднамеренные искажения и шум и строя глазковые диаграммы. «FM» действительно выигрывает.
Поправьте Гаула на Галуа. Глаза режет.
Причём делим мы не на что попало, а на определённый, так называемый «порождающий» полином. Откуда он берётся? Почему делится только сам на себя?Так мы его выбираем такой, чтобы делился только сам на себя. В поле вычетов по модулю 2 есть только два полинома первой степени: x и x+1. Перемножая их, можем получить x*x = x², x*(x+1) = x²+x, (x+1)*(x+1)=x²+1 — вот так, по модулю 2. А полином x²+x+1 получить умножением полиномов первой степени невозможно. Это и есть единственный неприводимый полином второй степени по модулю 2, который можно использовать, как порождающий для GF[4]. Аналогично, если перемножить все возможные полиномы второй степени на x и x+1, мы получим не все кубические полиномы. Не получится как раз тех самых полиномов, которые и можно использовать как порождающие.
НЛО прилетело и опубликовало эту надпись здесь
Было бы интересно еще почитать такое же простое объяснение, почему при таком построении деление получается операцией, обратной умножению.
В смысле, получается? Деление — по определению операция, обратная к умножению. То есть для решения уравнения x*a = b нужно поделить b на a. И деление в полях Галуа не связано с обычным числовым делением. Это умножение на обратный элемент x = b*a-1, где a-1 это такое значение, что a*a-1 = 1
А «1», в свою очередь, тоже не произвольный элемент, а такой, что для любого «a» из поля выполняется a*1=a.
А это требование, в свою очередь, является необходимым условием того, чтобы некоторое множество называлось «полем». Чтобы нечто было полем, надо, чтобы в нём был единичный элемент, т.е. такой, который не изменяет другие элементы при умножении.
А это требование, в свою очередь, является необходимым условием того, чтобы некоторое множество называлось «полем». Чтобы нечто было полем, надо, чтобы в нём был единичный элемент, т.е. такой, который не изменяет другие элементы при умножении.
2+2=4 в этом поле так же, как и в поле привычных нам, действительных чисел… (вообще сложение и вычитание для конкретно этого поля это просто побитовый XOR).
Что-то у вас не сходится. 2 xor 2 равно 0, а не 4.
Алгоритм не то, чтобы совсем новый, его ещё в первых CD применяли, но при этом, насколько мне известно, не потерявший своей актуальности и на данный момент.
Ты не поверишь, но его применяли нааамного раньше «первых CD» — с его помощью работал обмен фотографиями с Вояджером-2, запущенным 43 года назад. Да и собственно до сих пор работает, хотя это самый удаленный рукотворный объект… хотел написать «в нашей системе», но он ее уже покинул.
5 лет разницы между первым CD-проигрывателем и запуском Вояджер-2. Не то чтобы одновременно но и не нааамного. CD я привёл, как технологию, в которой точно знаю что использовалось кодирование Рида-Соломона, и о которой известно вообще всем. А о кодировании информации в космических коммуникациях не могу рассказывать уверенно.
Вообще, количество элементов поля это число не произвольное. Оно называется «характеристикой поля» и может быть либо простым числом, либо степенью простого числа (её называют «порядком поля», основание этой степени называют «основанием поля»).
Количество элементов поля и характеристика поля — это разные вещи, в общем случае не равные.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Программная реализация умножения в полях Галуа