Декодирование циклических кодов
Для обнаружения и исправления ошибок принятая комбинация делится на образующий многочлен g(х). Если остаток R(х) = 0, значит, комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Значение остатка совпадет с одним из опознавателей матрицы Н, который и укажет на местоположение ошибки по вектору ошибок.
1100001
1011
1110
1011
1010
1011
011 ошибка в четвертом разряде
Если ошибка содержится в одном из поверочных разрядов, то одночлен одиночной ошибки будет иметь степень, меньшую, чем степень образующего многочлена и совпадет с остатком от деления. При этом номер разряда остатка прямо укажет на номер искаженного поверочного разряда.
1101011
1011
1100
1011
1111
1011
1001
1011
010 ошибка во 2м контрольном разряде
Существует более общий алгоритм обнаружения и исправления ошибок:
1. Принятая комбинация делится на образующий многочлен g(x). Если остаток R(x)<>0 то определяется вес остатка w. Если вес остатка равен или меньше числа исправляемых ошибок t (w<=t), то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.
2. Если w>t, то производится циклический сдвиг на один символ влево и полученная после такого сдвига комбинация снова делится на образующий многочлен. Если вес полученного остатка w<=t, то циклически сдвинутую комбинацию складывают с остатком и затем после сложения циклически сдвигают в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получаем исправленную комбинацию.
3. Если после циклического сдвига на один символ по прежнему w>t, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига осуществляется деление сдвинутой комбинации на g(x) и проверяется вес остатка. При w<=t сдвинутую комбинацию складывают с остатком и производят обратных циклических сдвигов вправо столько, сколько было сделано влево.
Пример 4.1 Необходимо проверить принятый код 1101110, для g(x)=1011 и t=1.
1. Принятый код 1101110 делим на g(x), находим остаток R(x)=111, w=3
2. Код 1101110 сдвигаем влево на один разряд, получаем 1011101. Делим на образующий многочлен g(x). Находим остаток R(x)=101, вес w=2
3. Снова производим сдвиг влево, получаем 0111011. Делим на g(x). Остаток R(x)=001. w=1
4. Складываем сдвинутую комбинацию с остатком 0111011+001=0111010
5. Производим два циклических сдвига вправо
0111010 > 0011101 >1001110
В результате получили исправленную комбинацию.
Б
лок-схема
программы кодера(7,4)
нет д
а да
c[3]
= c[2] c[2]
= c[1]
c[3]
= (c[2] + g[3]+1) mod 2
c[1]
= (c[0] + g[1]+1) mod
2
Б
лок-схема
программы декодера(7,4)
нет д а да
c[3]
= c[2];
c[2]
= c[1];
c[1]
= a[i];
c[3]
= (c[2] + g[3] + 1) mod 2;
c[2]
= (c[1] + g[2] + 1) mod 2;
c[1]
= (a[i] + 1) mod 2;
нет да
Циклический
сдвиг влево
нет д а да
c[3]
= (c[2] + g[3] + 1) mod 2;
c[2]
= (c[1] + g[2] + 1) mod 2;
c[1]
= (a[i] + 1) mod 2;
c[3]
= c[2];
c[2]
= c[1];
c[1]
= a[i];
a[i]=(a[i]+c[7-i])mod2
