Главная Помехоустойчивое кодирование



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

(5.103)

Лх +Вх + С = О,

тле ASiS-iSi); В S2 S3s[ S4; С = S2 S4 (S).

Таким образом, уравнение (5.103), если оно разрешимо, задает пару корней; xi и Х2, соответствующих позициям ошибок, так что далее задача сводится к решению системы из Л + 2 линейных уравнений относительно весов е i, е 2, 6i, 62. - • • , €ft. Если окажется, что >l = fi = C=0, тов сообщении только одна ошибка. Если квадратное уравнение (5.103) не разрешимо над заданным полеМ Галуа или если не все его коэффициенты (а только некоторые) равны нулю, то в сообщении более двух ошибок.

Пример 5.19* Рассмотрим пример рещения системы уравнений над полем GF(2*) приЛ = 2,g = 1. Пусть заданы синдромы Sq = Z-; Si = £-Xj-; 52 = = S-x?; S3 = 2-х?,где1 = 1,2,..., {2g +h +4) и не все S,- = 0.

Процесс решения сводится к следующему:

вычисляем величины:

Ф = <71+а2; Тщаг; Лl=S2+SlФ\ A2 = SoT; В = Зз+82Ф + Т; A=Ai+A2;

проверяем АнВ нл равенство нулю:

если Л = = О, то считаем, что ошибок нет, а есть лишь стирания, которые

исправляются обычным образом;

если А = 0,В Ф О или А Ф ОВ = Ото ошибок более двух; если А Ф Of В Ф О то место ошибки х = В/А, а веса стираний

Aia. +Si Ф. +А2Х

е = -1-L- .

ФФ.

где Ф. = {x + aj)aj-, / = 1,2, т.е, Фх = (x + ai)ai; Ф2 = (х +02)02 ; AiOi + SlФl+А2Х i4ia2+«1*2+2

ei---; е2 = -.

ФФ] ФФ2

Величина ошибки е = 5о + + €2.

в общем случае исправления h стираний и > 2 ошибок удобнее пользоваться методами, изложенными в гл. 6,



ГЛАВА ШЕСТАЯ

КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ КОДОВ РИДА - СОЛОМОНА

НАД ПОЛЯМИ ГАЛУА

6-1. МОДЕЛЬ СИСТЕМЫ ТЕЛЕПЕРЕДАЧИ (ЗАПИСИ - ВОСПРОИЗВЕДЕНИЯ) ЦИФРОВОЙ ИНФОРМАЦИИ

воспроизведения

Обобщенная структура системы. На рис. 6.1 п структурная схема систем телепередачи и записи - цифровой информации. Кодер преобразует сообщение Q в кодовое слово V, которое подвергается канальной модуляции. В системах телепередачи модулятор вырабатьюает физические сигналы у, предназначенные для пересылки по некоторому реальному каналу связи и обеспечивающие согласование полосы частот передаваемого сигнала

с частотной полосой пропускания канала,

В системах записи - воспроизведения информации (как правило, двоичной) роль канала играет носитель информации: магнитная лента, диск, грампластинка, полупроводниковые запоминающие устройства

Сообщение Q

Канальнь1Й демодупятор

Кодер

Внешний

кодер


Внутренний декодер

Схема опознания ош ибочного симвопа

Метка стирания

Внутренний

Канальный

кодер

модулятор

Помехи

Канал

Декодер

Де интерливер

Внешний декодер

Сообщение Q

Рис. 6.1. Структура системы телепередачи (записи-воспроизведения) дискретной

информации



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

При использовании поля GF(2) двоичные комбинации дайны г преобразуются в ri-разрядные {гу >г) двоичные комбинации, в которых число нулей между двумя единицами ограничено сверху и снизу. Например, в системах цифровой грамзаписи с .бесконтактным считыванием (с помощью луча лазера) 8-разрядные элементы поля GF(2) при канальной модуляции преобразуются в 14-разрядные двоичные комбинации [38].

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

На приетушом конце при воспроизведении сообщений rj-разрядные двоичные комбина1щи у с помощью канального демодулятора, также представляющего собой логическую комбинационную схему, обратно преобразуются в г-разрядные комбинации - в элементы поля GF(2), образующие, возможно, искаженное кодовое слово v

Так как >/*, то из 2 комбина!!ЩЙ канального кода используется лишь их часть (2 штук). Это позволяет возложить на канальный демодулятор также функцию опознания ошибочной rj-разрядной

комбинации, если она не принадлежит к списку 2 рабочих комбинаций.

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

Декодер исправляет стирания и ошибки, если их число не нарушает условия 6?>2r+d + l, где d ~ кодовое расстояние кода; г - число стираний; v - число опшбок.



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 [78] 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0134