Программная реализация умножения в полях Галуа

Захотелось мне как-то сделать более надёжной передачу информации через радиоканал. Это не какой-то промышленный проект, или что-то другое серьёзное. Это скорее для хобби и саморазвития. Сказалась травма детства — отсутствие нормально работающей радиоуправляемой машинки. С тех пор мне всегда хотелось уметь легко и непринуждённо управлять чем угодно по радио...


Итак, я отвлёкся. В детстве-юношестве для помехоустойчивого кодирования можно было бы применить контроль чётности по матричному методу, но сейчас это не серьёзно. Полистав интернет я решил остановиться на кодировании по методу Рида-Соломона. Алгоритм не то, чтобы совсем новый, его ещё в первых CD применяли, но при этом, насколько мне известно, не потерявший своей актуальности и на данный момент. В этой статье о самих кодах Рида-Соломона я не буду сильно распространяться – это за меня на Хабре сделали много раз и много кто. Здесь я хочу описать реализацию алгоритма умножения в GF[256]. Тем не менее, чтобы не заставлять читателя прыгать по ссылкам, кратенько опишу зачем вообще приходится иметь дело с полями Галуа.


Избыточное кодирование Рида-Соломона это о матрицах. Мы используем матрицы при кодировании и при декодировании. В этих процессах присутствуют как операции умножения матриц, так и операции нахождения обратных матриц — деления. Деление здесь требуется не приблизительное-целочисленное, а самое настоящее, точное. А точное деление для компьютера нерешаемая задача: один разделить на три это ноль целых и бесконечное количество троек после запятой, но память при этом 640 килобайт хватит каждому.


Галуа жил в начале 19 века, жил очень мало (21 год, вообще про его личность история интересная, но сейчас не об этом). Его работы очень сильно пригодились при цифровом кодировании. Конечное поле Галуа — это набор чисел от нуля до n. Суть и интересность этих полей в том, что для элементов этого набора можно определить операции сложения-умножения-вычитания-деления такие, что результат операции будет находиться в самом этом поле. Например, возьмём набор (поле):

$[0,1,2,3,4,5,6,7]$

$2 \cdot 2=4$ в этом поле так же, как и в поле привычных нам, действительных чисел. А вот 5+6 равно не 11, как мы привыкли, а 5+6=3, и это замечательно! 3 входит в это поле (вообще сложение и вычитание для конкретно этого поля это просто побитовый XOR). Для умножения и деления тоже выполняется правило: результат от умножения или деления любых двух чисел из поля (набора… Далее буду говорить только «поле») будет находиться в этом поле.

Вообще, количество элементов поля это число не произвольное. Оно называется «характеристикой поля» и может быть либо простым числом, либо степенью простого числа (её называют «порядком поля», основание этой степени называют «основанием поля»). К счастью, количество чисел, которое можно зашифровать с помощью одного байта равно 256, а это два (простое число) в степени 8, и мы можем принять множество всех возможных значений байта за конечное поле Галуа. По умному оно называется GF[256], GF значит Galois Field.


Так вот. Если использовать арифметику в поле Галуа над байтами, то при делении матриц, состоящих из байтов никогда не получится чисел, которые нельзя записать в один байт, а значит то, как реализовывать «в железе» (я использую stm32 в основном) алгоритмы кодирования-декодирования становится немного понятнее.


Немного об арифметике. Сложение и вычитание, как упоминалось ранее, это одна и та же операция в полях Галуа (это точно верно для полей с основанием 2), и реализуется она как побитовый XOR.

$A+B = A \operatorname{xor} B$

$A-B = A \operatorname{xor} B$

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

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


Пример:

$5=101_2=1\cdot x^2+0\cdot x^1+1\cdot x^0=x^2+1$


Далее полиномы перемножаются по правилам перемножения полиномов, то есть каждый член в первой скобке умножается на каждый член во второй, но не просто так, а с учётом того, что коэффициент не может быть больше одного.

$x^2+x^2=0$

$x^2+x^2+x^2=x^2$

$x^2+x^2+x^2+x^2=0$

То есть коэффициенты складываются по модулю 2. Пример умножения в GF[8]:

$6\cdot 3 = 110_2\cdot 11_2= (1\cdot x^2+1\cdot x^1+0\cdot x^0)\cdot (1\cdot x^1+1\cdot x^0)=$

$ =(x^2+x)(x+1)=x^2\cdot x+x^2\cdot 1+x\cdot x+x\cdot 1=$

$=x^3+x^2+x^2+x$

Далее «складываем» (в кавычках — потому, что по модулю 2) подобные члены, и получаем $x^3+x$, что мы переводим в обычное число $1010_2=10$.

Так как это умножение мы подразумевали в GF[8], то число 10 в результате должно вызвать недоумение: «Как же так? 10 нету в наборе [0,1,2,3,4,5,6,7]». И да. Тут кроется ещё ложка дёгтя. Если получается такая ситуация (результат перемножения не в поле), то далее мы проводим операцию деления по правилам полиномов. Причём делим мы не на что попало, а на определённый, так называемый «порождающий» полином. Откуда он берётся? Почему делится только сам на себя? И прочие вопросы я оставлю без ответа (не потому, что жадный, а потому что не хочу вводить в заблуждение, сам плохо понимаю). Скажу лишь, что для конкретного поля Галуа есть один или несколько таких подходящих порождающих полиномов. Для GF[8] их всего два: 11 и 13, то есть 1011 и 1101 или $x^3+x+1$ и $x^3+x^2+1$


И так, чтобы умножить 6 на 3 в поле GF[8] недостаточно лишь перемножить два многочлена. После перемножения надо результат $x^3+x$ поделить на один из возможных порождающих многочленов. Здесь мы выберем $x^3+x+1$. Правила деления многочленов столбиком здесь похожи на те, которые мы должны помнить из школьной программы, но во-первых «должны», а во вторых они всё же отличаются. Поясню на нашем примере. Берём старшую степень делимого, в нашем случае это $x^3$ и делим на старшую степень делителя (здесь это также $x^3$). Записываем результат 1. Далее получившийся результат умножаем на весь делитель (получается $x^3+x+1$). Это мы записываем под делимым, и проводим вычитание (а в поле GF[8] вычитание и сложение есть одно и то же) то есть $(x^3+x) +(x^3+x+1)$. Сложение проводим по модулю 2, этому нас обязывает работа в поле, и получаем 1. Далее этот результат мы опять бы делили на порождающий многочлен таким же образом, если бы степень получившегося результата (после вычитания) была бы больше или равной степени делителя (порождающего многочлена). А так как степень меньше, то мы за результат деления принимаем остаток от деления, то есть результат вычитания(сложения – здесь это одно и тоже), то есть 1.


Всё. $6 \cdot 3 = 1$ для GF[8] c порождающим полиномом 11.


Казалось бы всё непросто. С такими сложностями нужно много-много кода и суперкомпьютеры и вообще проще хранить таблицу умножения как массив 256х256 (ну или 8х8, смотря какое поле мы используем), Но всё не так плохо. У полей Галуа есть ещё одно замечательное свойство, и связано оно с операцией возведения в степень. Так как возведение в степень — это просто последовательное умножение, то результат возведения в степень так же является элементом поля Галуа. Также для любого поля верно утверждение, что в нём есть минимум один элемент, степени которого содержат в себе всё поле (кроме 0). То есть, если взять для GF[8] число 2, то
$2^0=1\;\;\;\;\;2^7=1$
$2^1=2\;\;\;\;\;2^8=2$
$2^2=4\;\;\;\;\;2^9=4$
$2^3=3\;\;\;\;\;2^{10}=3$
$2^4=6\;\;\;\;\;2^{11}=6$
$2^5=7\;\;\;\;\;2^{12}=7$
$2^6=5\;\;\;\;\;2^{13}=5$

Если присмотреться, то можно обратить внимание, что любое число от 1 до 7 можно однозначно представить как 2 в какой либо степени. Так же свойство операции возведения в степень в этом поле таково, что $2^7=2^0$ ещё $2^8=2^1$, $2^9=2^2$ и так далее. Это значит, что 2 в любой степени может быть представлено в виде двойки в степени от нуля до 6 с помощью операции получения остатка от деления на 7 в случае положительной степени и простой формулы $2^{-x}=2^{(7-(x\: mod\:7))}$, если показатель — отрицательное число


Собственно, если вспомнить свойство умножения степеней, то умножение чисел многократно упрощается. И чтобы умножить 6 на 3 мы теперь смотрим, в какой степени двойка равна 6 и в какой степени двойка равна 3, складываем степени и смотрим результат — два в какой-то степени, которую можно представть как 2 в степени от 0 до 6 пример:

$6\cdot 3=2^4\cdot 2^3=2^{(4+3)} = 2^7 = 2^0 = 1 $

С делением тоже всё становится предельно понятно:

$3/6=2^3/2^4=2^{(3-4)} = 2^{-1} = 2^{(7-(1\: mod\:7))} = 2^6 = 5 $


И вроде бы вот оно! счастье программиста — реализация арифметики в поле Галуа — пара строчек кода, не нужно заморачиваться с полиномами… Да и быстродействие такого кода будет высоким, но тут я столкнулся с ещё одной проблемой: Таблицу степеней двойки в поле GF[8] с порождающим полиномом 11 найти легко. Даже на этом ресурсе есть. А вот таблицу степеней для GF[256] я с нахрапа не нагуглил, так что решил её составить самостоятельно, C# мне в помощь. Пришлось реализовать алгоритм умножения по правилам полиномов.

Привожу рабочую функцию перемножения для GF[2^n] c произвольным полиномом. Ограничение — я испольую 32-битную арифметику, так что n должно быть меньше 16. Также здесь добавлена функция поиска номера старшего бита числа



private uint GetLeadBitNum(UInt32 Val) {
    int BitNum = 31;
    uint CmpVal = 1u << BitNum;
    while (Val < CmpVal) {
        CmpVal >>= 1;
        BitNum--;
    }
    return (uint)BitNum;
}
private uint Galois_b2_ext_mult(uint m1, uint m2, uint Poly) {
    if (0 == m1 || 0 == m2) { return 0; }
    uint m1_tmp = m1;
    uint m2_tmp;
    uint m1_bit_num = 0;
    
    //Перемножение двух полиномов, при использовании арифметики по модулю 2 достаточно простое занятие.
    //перебираем единички и нолики (для каждого бита первого числа перебираем все биты второго (или наоборот)), складываем номера позиций битов,
    //но не всегда, а только когда оба перебираемых бита - единицы, и инвертируем бит результата под номером, равном сумме позиций для данного шага перебора
    //(инверсия - это прибавление единицы по модулю 2)
    uint PolyMultRez = 0;

    while (m1_tmp != 0) {
        uint bit_m1 = (m1_tmp & 1u) == 0u ? 0u : 1u;
        m1_tmp = m1_tmp >> 1;
        m2_tmp = m2;
        uint m2_bit_num;
        m2_bit_num = 0;
        while (m2_tmp != 0) {
            uint bit_m2 = (m2_tmp & 1u) == 0u ? 0u : 1u;
            m2_tmp = m2_tmp >> 1;
            if ((bit_m1 != 0) && (bit_m2 != 0)) {
                int BitNum = (int)(m2_bit_num + m1_bit_num);
                PolyMultRez ^= 1u << BitNum;
            }
            m2_bit_num = m2_bit_num + 1;
        }
        m1_bit_num = m1_bit_num + 1;
    }

    //Тут есть результат умножения полиномов PolyMultRez. Осталось найти остаток от деления на выбранный порождающий полином.
    //Деление полиномов происходит так: Берём старшую степень делимого, и вычитаем старшую степень делителя. 
    //Получаем число - степень частного
    //Теперь перемножаем, а по сути, просто прибавляем к каждой степени делителя степень получившегося частного
    //и повторяем всё по кругу, пока степень делимого не окажется меньше степени делителя
    uint TmpDivisor_lead_bit_n;
    uint TmpQuotient;
    uint TmpDivisor = Poly;
    uint TmpDividend = PolyMultRez;
    uint TmpDividend_LeadBitNum;
    uint TmpMult_bitNum;
    uint TmpMult_rez;

    TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);
    TmpDivisor_lead_bit_n = GetLeadBitNum(TmpDivisor);

    while (TmpDividend_LeadBitNum >= TmpDivisor_lead_bit_n) {

        TmpQuotient = (TmpDividend_LeadBitNum - TmpDivisor_lead_bit_n);

        TmpMult_bitNum = 0;
        TmpMult_rez = 0;
        while (TmpDivisor != 0) {
            uint bit_TmpMult = (TmpDivisor & 1u) == 0u ? 0u : 1u;
            TmpDivisor >>= 1;
            TmpMult_rez ^= bit_TmpMult << (int)(TmpQuotient + TmpMult_bitNum);
            TmpMult_bitNum = TmpMult_bitNum + 1;
        }
        TmpDividend = TmpDividend ^ TmpMult_rez;
        TmpDivisor = Poly;
        TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);
    }            
    //Результат умножения числел есть остаток от деления произведения многочленов на порождающий полином.
    return TmpDividend;
}

Теперь, с помощью приведённой выше функции можно составить таблицу степеней двойки для нужного мне GF[256] и написать модуль арифметики Галуа для stm32 с использованием двух таблиц по 256 — одна для прямого, вторая для обратного преобразования числа в его степень. К самой реализации кодирования Рида-Соломона я ещё даже не приступал, но, когда будет готово, думаю поделюсь здесь же. Надеюсь, получится короче.

Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 39

    +15

    А почему вы Галуа называете Гаула ?

      +2
      Еще суровее — он Гаул.
      Это как Саул, только Гаул. :)
        0

        Ёлки, я даже полез в Гугл гуглить, неужели всю жизнь я называл тов. Галуа неправильно. Оказалось, правильно. Поставьте плюс те, кто сделал так же. :)


        Гаул, наверное, его незаконнорожденный брат. Великий Гаул положил поле в баул.

          0
          В первый раз, когда разбирался с темой, я прочитал «поле ГаУла». Так и запомнил. Так и изложил. Не иеемт занчнеия, в каком порядке располоежны буквы, блин.
            +2
            имеет
              +2
              Так я и не писал, что не имеет. Я написал, что «не иеемт». Многие подвержены этой ошибке, и я, к сожалению, не исключение.
                +1
                Но ради уважения, надо хотя бы имена правильно писать.
              0
              Конечно не имеет, вот когда вам придёт ЗП не 50000р, а 00050р бухгалтер тоже скажет: «да какая разница как расположены цифры»
            +1
            С таблицами степеней и логарифмов гораздо проще выходит, а произвольная размерность поля на практике нигде не нужна.
            Лет 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]);
            }
            
            
              0
              Всё верно. Через логарифмы много проще. Только вот не удалось мне найти таблицы степеней для GF[256].
                +1
                Таблицу степеней 2 построить просто: каждый раз умножаем на 2 (как обычно, сдвиг влево на 1 разряд), и если результат >= 256 делаем xor с порождающим полиномом.
                  +1
                  Ну что-ж… Если бы эти две строчки нагуглились мне раньше, то не пришлось бы с полиномами ковыряться, чтобы табличку составить. Грустно быть «альпинистом, взобравшимся на неприступный горный пик и обнаружившим там отель, ресторан и вертолётную площадку»
                  0
                  Так это-же очевидно:

                  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;
                  }
                0
                Спасибо за статью, отличная тема! Наконец-то доходчивое объяснение сути полей Галуа.

                Касательно надёжности радиосвязи: не кодированием единым она достигается. Какие ещё меры вы собираетесь реализовывать? Какие методы модуляции?
                  0
                  Проверять работу кодироваия буду на микросхеме LT8920 – интегрированный приёмо-передатчик с интерфейсом SPI. Модуляция у него GFSK на 2,4 ГГц. Там даже встроенная проверка CRC есть, и реализовано кивитирование. Просто захотелось иметь в коллекции самописных C++ библиотек собственную реализацию кодирования Рида-Соломона. Интересно разобраться.
                    +1
                    Просто захотелось иметь в коллекции самописных C++ библиотек собственную реализацию кодирования Рида-Соломона. Интересно разобраться.

                    Когда-то давно сам разбирался с этим. Для микроконтроллеров понял, что обобщенные варианты достаточно сложны и не приносят пользы, за исключением возможности варьировать параметры. Поэтому я сделал модель, выбрал нужные параметры кодера, зафиксировал их, а потом сделал реализацию со сквозной оптимизацией кодека типа (15,11) в поле GF(256). Правда в моем случае декодер работал на более мощной железке, но зато кодеру не нужно было почти ничего: для ускорения можно было использовать 8 таблиц по 16 байт, но если памяти не хватало — можно было вычислять всё вообще без использования каких-либо таблиц, но чуть медленнее. Вся схема чудесно трудилась кажется на MSP430C1132 (не помню точно номер за давностью лет), где было всего-то 128 байт памяти.
                  +2
                  Какое-то сложное получилось обобщенное умножение, есть же варианты проще. И через таблицы степеней/логарифмов и через композитные поля и через разделение на группы битов. И все это хорошо ложится на микроконтроллеры, а композитные поля еще полезны при реализации в железе.

                  Прямо хоть самому статью написать про это. Только не знаю, будет ли интересно кому-нибудь? Ведь вроде же вся информация и так есть в разнообразных научных статьях.
                    +1
                    А было бы интересно посмотреть
                    0
                    Есть ли у вас модель помех используемого радиоканала? Под ней понимаются не только характерные для имеющейся аппаратуры искажения сигнала, но и эфирные помехи в той местности, где аппаратура будет работать.

                    Иначе ваше шумоподавление будет хорошо работать за городом, где радиошума мало (и шумоподавление в общем то не очень нужно), но будет плохо работать в городе (где много источников помех).
                      0
                      Нет. Радиоканал — «на аутсорсе». Им занимается копеешный интегрированный приёмо-передатчик. С моей стороны SPI только и цифры.
                        +1
                        Какой чип вы используете?

                        Что вы посылаете в передатчик, и что приходит из приемника?
                        Дело в том, что полезные данные (payload) уходят в эфир в обрамлении дополнительной информации (overhead).

                        Состав посылки:

                        1) Преамбула. Обычно используется меандр (1010101010101.....). Он нужен для настройки АПЧ для ЧМ приемника. Если у вас канал АМ — преамбула не обязательна.

                        2) Синхропосылка (иногда называется маркер). По синхропосылке приемник выставляет битовую и байтовую синхронизацию. Длина синхропосылки примерно от 8 до 32 бит, ее содержимое не случайно — оно должно иметь хорошую автокорреляцию само с собой. Важный для вас момент — где то (в микросхеме?) определяется допустимое количество ошибок в синхропосылке, которое определяет и допустимое соотношение сигнал/шум, выше которого вы прыгнуть не сможете.

                        Синхропосылка должна быть сбалансирована по количеству 0/1, поскольку сразу после определения её наличия ЧМ приемник фиксирует АПЧ, и до конца всей посылки частота приема не изменяется. Это позволяет дальше передавать любые несбалансированные данные.

                        АПЧ можно не отключать, если данные передаются кодом «Манчестер», но вы за это заплатите удвоением времени передачи.

                        3) Собственно полезные данные. Если длина посылки переменная, то перед данными должен идти байт длины посылки (как в строках в Паскале). Если длина посылки постоянная, эту длину надо объяснить микросхеме как в приемнике, так и в передатчике.

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

                        4) Контрольная сумма, от 8 до 32 бит.

                        И вот тут вопрос — выдаст ли приемник вам посылку, если контрольная сумма будет неверная? Если нет — у вас нет возможности осуществлять шумоподавление в принципе.

                        В результате обычно получается, что вам нужно осуществлять «закат солнца вручную». То есть переводить приемник в прозрачный режим, когда он высыпает из себя всё, что принимает из эфира, и вручную разбирать посылку с шумоподавлением. Не забывая вовремя управлять аппаратной частью (включать/отключать АПЧ).

                        Без модели помех вы скорее всего получите хорошее подавление случайных помех (искажение N бит на длине M), на которые и рассчитаны стандартные алгоритмы (при превышении N исправления данных не будет). В то же время промышленные помехи выглядят иначе — они как раз выбивают относительно большое количество бит подряд (надо набрать статистику примерно за неделю, чтобы понять сколько именно у вас в эфире). Против этого используют скремблирование — перемешивание байт при передаче (после добавления избыточности) с обратным процессом на приемнике (до шумоподавления). При этом длинная помеха «размешивается» по длине, что позволяет осуществить шумоподавление.
                          0
                          И вот тут вопрос — выдаст ли приемник вам посылку, если контрольная сумма будет неверная? Если нет — у вас нет возможности осуществлять шумоподавление в принципе.
                          Приёмопередатчик LT8920. В случае битых данных, он выдаёт посылку, и выставляет бит CRC err. Так что не придётся «закатывать вручную». А про скремблирование — сам думаю. Дополнить Рида-Соломона скремблером. Так, вроде, в CD дисках сделано. Их можно царапать широкими царапинами.
                            +1
                            Обратите внимание на случай искажения байта длины посылки. Это очень критичное для шумоподавления место. Возможно будет проще переключиться на режим с фиксированной длиной и передавать длинные данные в несколько пакетов.
                              0
                              Согласен. Собственно даже без «шумоподавления» я предпочитаю фиксированную длину одной посылки. Вообще помехоустойчивое кодирование с восстановлением данных тоже гарантией мне не кажется. И лучше всего — это квитирование каждой посылки с автоповтором, в случае отсутствия ответа. Но это не значит, что не нужно для себя изучить помехоустойчивое кодирование. Вдруг придётся передавать на расстояния, на которых квитанция будет идти несколько минут.
                                +1
                                Наличие квитирования зависит от задачи. Вы можете передавать команду или разовые события которые пропустить нельзя. А можете передавать состояние объекта с медленно изменяющимися данными — и в этом случае пропуски не важны, следующая передача доставит нужные данные.

                                Изучение — это правильно. В свое время я даже патент получил на новый способ помехоустойчивого кодирования :).
                              0
                              У этого чипа есть встроенная возможность исправления ошибок — FEC13 и FEC23, без подробного описания, что это такое.
                              0
                              АПЧ можно не отключать, если данные передаются кодом «Манчестер», но вы за это заплатите удвоением времени передачи.

                              Не манчестером единым. Есть и более эффективные сбалансированные коды, например, 8b/10b. Время передачи увеличивается всего на 12,5%, а не вдвое, как у «Манчестера». Я даже реализовал этот метод для записи сигналов на магнитофон ZX-Spectrum. Заработало. Правда, помехоустойчивость оказалась хуже, чем у оригинального кода «FM», т.е. передача нуля последовательностью 10, а единицы — 1100.

                              До сих пор не понимаю, как это произошло. Но факт. «Манчестер» тоже испытывали, он показал близкую к 8b/10b и недостаточную эффективность. Ещё я моделирование проводил, внося в сигнал преднамеренные искажения и шум и строя глазковые диаграммы. «FM» действительно выигрывает.
                          +1
                          Поправьте Гаула на Галуа. Глаза режет.
                            +1
                            Причём делим мы не на что попало, а на определённый, так называемый «порождающий» полином. Откуда он берётся? Почему делится только сам на себя?
                            Так мы его выбираем такой, чтобы делился только сам на себя. В поле вычетов по модулю 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, мы получим не все кубические полиномы. Не получится как раз тех самых полиномов, которые и можно использовать как порождающие.
                              0
                              Есть набор инструкций CLMUL, который делает именно это
                                0
                                Жаль, что нет такой инструкции в cortex-m3.
                                  0
                                  А инструкции деления не появилось?
                                  +1

                                  Было бы интересно еще почитать такое же простое объяснение, почему при таком построении деление получается операцией, обратной умножению.

                                    +2
                                    В смысле, получается? Деление — по определению операция, обратная к умножению. То есть для решения уравнения x*a = b нужно поделить b на a. И деление в полях Галуа не связано с обычным числовым делением. Это умножение на обратный элемент x = b*a-1, где a-1 это такое значение, что a*a-1 = 1
                                      0
                                      А «1», в свою очередь, тоже не произвольный элемент, а такой, что для любого «a» из поля выполняется a*1=a.

                                      А это требование, в свою очередь, является необходимым условием того, чтобы некоторое множество называлось «полем». Чтобы нечто было полем, надо, чтобы в нём был единичный элемент, т.е. такой, который не изменяет другие элементы при умножении.
                                    0
                                    2+2=4 в этом поле так же, как и в поле привычных нам, действительных чисел… (вообще сложение и вычитание для конкретно этого поля это просто побитовый XOR).

                                    Что-то у вас не сходится. 2 xor 2 равно 0, а не 4.

                                      +1
                                      Верно. Попутал 2 x 2 и 2+2. Сейчас поправлю, спасибо.
                                      0
                                      Алгоритм не то, чтобы совсем новый, его ещё в первых CD применяли, но при этом, насколько мне известно, не потерявший своей актуальности и на данный момент.

                                      Ты не поверишь, но его применяли нааамного раньше «первых CD» — с его помощью работал обмен фотографиями с Вояджером-2, запущенным 43 года назад. Да и собственно до сих пор работает, хотя это самый удаленный рукотворный объект… хотел написать «в нашей системе», но он ее уже покинул.
                                        0
                                        5 лет разницы между первым CD-проигрывателем и запуском Вояджер-2. Не то чтобы одновременно но и не нааамного. CD я привёл, как технологию, в которой точно знаю что использовалось кодирование Рида-Соломона, и о которой известно вообще всем. А о кодировании информации в космических коммуникациях не могу рассказывать уверенно.

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое