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

(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 - число опшбок.