2. Метод контрольных чисел (синдромное декодирование)

Идея этого метода применительно к бинарным кодам с коррекцией одиночных ошибок была изложена Хэммингом [176]. Затем она была обобщена и распространена на более сложные случаи (160—162], в том числе на небинарные коды (см, например, [29, 56]). Следует отметить, что исследования, проводимые в этих направлениях различными авторами, отличаются лишь по форме, но не по существу.

Пусть задан код

(VII.2.1)

и по каналу передана одна из его комбинаций

(VII.2.2)

где, напомним, проверочный символ

(VII.2.3)

( — коэффициент при независимой переменной в линейной форме ).

Предположим, что принята комбинация

(VII.2.4)

Для удобства изложения запишем вектор шума в виде

(VII.2.5)

Тогда в полном соответствии с (VII.1.1) и (VII.1.2) информационные символы комбинации (VII.2.4)

(VII.2.6)

а ее проверочные символы

(VII.2.7)

Вычислим значения проверочных символов , используя для этой цели информационные символы принятой комбинации и соотношения (VII.2.3):

(VII.2.8)

Найдем разности:

(VII.2.9)

Совокупность элементов называют контрольным числом или синдромом [29]. По виду контрольного числа, как будет показано ниже, можно сделать не только заключение о том, содержит ли принятая комбинация трансформированные символы, но и определить их место и характер искажения*.

Подставляя (VII.2.6) и (VII.2.7) в (VII.2.9) найдем

(VII.2.10)

Отсюда видно, что элементы контрольного числа зависят только от значения компонент вектора шума. Другими словами, контрольное число инвариантно относительно комбинаций кода (VII.2.1).

Теорема VII.1 . Все элементы контрольного числа равны нулю тогда (и только тогда), когда принятая комбинация (VII.2.4) совпадает с одной из комбинаций кода (VII.2.1).

Действительно, из (VII.2.10) следует, что если ,

то

(VII.2.11)

т. е. символ связан с первыми символами комбинации Е соотношением, характерным для -го проверочного символа комбинаций данного кода (VII.2.2). Другими словами, шумовая комбинация Е совпадает с одной из комбинаций кода, в силу чего и принятая комбинация принадлежит коду.

Анализ показывает, что если в векторе Е только одна из компонент , то

(VII.2.12)

в частности, при

(VII.2.13)

Отсюда видно, что каждому из возможных искажений -го информационного символа соответствуют контрольные числа, представляющие собой результат умножения на компонент вектора (VII.2.13) (всевозможным искажениям -го информационного символа соответствует система линейно зависимых векторов).

Если же вектор Е таков, что лишь его компонента , то

(VII.2.14)

в частности, когда совпадает с элементом, обратным единице данного поля , мы имеем

(VII.2.15)

Таким образом, номер позиции контрольного числа, на которой располагается отличный от нуля элемент, совпадает с номером трансформированного проверочного символа, причем является элементом, обратным .

Выпишем в виде матрицы коэффициенты при независимых переменных в линейных формах (VII.2.2) и дополним ее единичной матрицей, каждая строка которой умножена на :

(VII.2.16)

Матрицу (VII.2.16) условимся называть контрольной, ибо первые ее строк — контрольные числа, соответствующие изменению на +1 -го информационного символа, a k последние строк определяют контрольные числа, соответствующие изменению на ту же величину -го роверочного символа.

В силу линейности операций, используемых для вычисления элемента , контрольное число, соответствующее различным искажениям символов комбинации, может быть найдено как некоторая не тривиальная сумма строк контрольной матрицы (VII.2.16).

Теорема VII.2. Если найти линейную комбинацию строк (VII.2.16), такую, что она будет совпадать с вычисленным контрольным числом, то номера этих строк совпадут с номерами поврежденных позиций, а коэффициенты, с которыми они складывались, определят, как искажен символ, стоящий на соответствующей позиции. (Для того чтобы исправить поврежденный символ, достаточно найти элемент, противоположный каждому из указанных коэффициентов, и прибавить его к соответствующему символу принятой комбинации.)

Обратим внимание на два обстоятельства. Во-первых, число -значных векторов типа (VII.2.9) равно , и, следовательно, возможное число корректируемых ошибок принципиально не может быть больше . Во-вторых, каждое контрольное число не однозначно определяет характер искажения принятой комбинации [одно и то же контрольное число может быть получено в результате различных линейных комбинаций строк матрицы (VII.2.16)].

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

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

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

Теорема VII.3. Множество шумовых комбинаций корректируется данным кодом, если, во-первых, не совпадает ни с одной из комбинаций данного кода и, во-вторых, разность двух любых векторов и также не образует комбинацию кода.

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

Зафиксируем два вектор-шума: и . Выпишем их разность:

(VII.2.17)

где

(VII.2.18)

Контрольные числа, соответствующие векторам и определяются формулами (VII.2.10), причем их элементы имеют вид:

(VII.2.19)

(VII.2.20)

(VII.2.21)

где .

Анализ этих выражений приводит к выводу:

(VII.2.22)

Таким образом, контрольные числа (VII.2.19) и (VII.2.20) не будут совпадать, если среди элементов разностного контрольного числа (VI1.2.21) — (VII.2.22) окажется хотя бы один отличный от нуля. В нашем случае это обстоятельство как раз и имеет место, ибо разностный вектор по условию не принадлежит коду, и поэтому согласно теореме VII.1 среди элементов его контрольного числа всегда найдется по крайней мере один отличный от нуля.

Только что доказанное положение широко используется в теории кодирования. В тех или иных вариантах оно содержится в работах [83—85, 159—162].

Следствие 1 (теоремы VI1.3). Каждое контрольное число может быть получено в результате различных искажений символов кодовой комбинации.

Действительно, пусть шумовой комбинации соответствует некоторое контрольное число, тогда то же самое контрольное число будет получено и при другой шумовой комбинации , если

(VII.2.23)

или

(VII.2.24)

где — произвольная комбинация данного кода.

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

Соотношение (VI1.2.24) позволяет однозначно разбить множество всех -значных комбинаций на непересекающихся подмножеств (всего имеется различных контрольных чисел). Заметим, что одно из этих подмножеств будет совпадать с кодом (случай, когда контрольное число равно нулю).

Указанные подмножества обладают свойствами, присущими так называемым в алгебре классам смежности. Поэтому иногда теорема VII.3 формулируется так: множество шумовых комбинаций корректируется данным кодом, если каждая из них принадлежит разным классам смежности. Таким образом, процесс исправления ошибок методом контрольных чисел в общем случае протекает так. На приемном конце в виде таблицы записываются контрольные числа и соответствующие им шумовые комбинации (каждому контрольному числу ставится в соответствие одна и только одна шумовая комбинация из класса смежности, определенного данным контрольным числом)*. Принятая комбинация запоминается в специальном устройстве памяти. Затем вычисляется контрольное число, и если окажется, что оно отлично от нуля, то с помощью указанной таблицы находится соответствующая ему шумовая комбинация. Последняя вычитается из , на чем и заканчивается процесс коррекции ошибок. Оригинальная реализация табличных способов декодирования по методу контрольных чисел пятизначных кодов с и предложена в работе [49]. Эти же вопросы обсуждены в [156—158]. Хэмминг [176] на примере семизначного бинарного кода с разработал метод, при котором контрольные числа совпадают с двоичной записью номера поврежденного символа. Подобного рода идеи могут быть реализованы применительно к ряду кодов с основанием . Наконец, заметим, что метод контрольных чисел допускает множество модификаций, основанных на структурных особенностях контрольных чисел, соответствующих тем или иным группам ошибок, и на том, что для правильного опознания переданного сообщения достаточно исправить ошибки в информационных символах принятой комбинации.

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

Конструктивные методы решения подобной задачи в общем случае даже для простейших каналов в настоящее время неизвестны, а их поиск осложняется тем, что корректирующие возможности кода (содержательность смежных классов) зависят не только от выбора линейных форм, но и от способа упорядочения этих форм по позициям, хотя последнее обстоятельство не влияет на величину

Примеры: Рассмотрим семизначный бинарный код:

(VII.2.25)

Комбинации этого кода отличаются одна от другой точно в четырех позициях и образуют нулевой класс смежности (см. табл. VII.1).

Контрольная матрица анализируемого кода в соответствии с (VII.2.16) имеет вид [в поле ]

(VII.2.26)

Если принятую комбинацию записать в виде

(VII.2.27)

то согласно (VII.2.10)

(VII.2.28)

Всевозможные контрольные числа выписаны во второй строке табл. VII.1. Под каждым из них приведены элементы соответствую, щего класса смежности, которые находились следующим образом.

Таблица VII.1

Сначала определялась одна (любая) шумовая комбинация, приводящая к данному контрольному числу, а затем на основе формулы (VII.2.24) находились остальные элементы класса смежности.

Эти операции легко выполняются с помощью проверочной матрицы (VII.2.26). Первая ее строка совпадает с контрольным числом, которое образуется при искажении первого информационного символа . Прибавляя к найденной таким образом шумовой комбинации поочередно все комбинации кода (VII.2.25) (комбинации нулевого класса смежности), получим все элементы первого класса смежности. Вторая строка матрицы (VII.2.26)совпадает с контрольным числом, соответствующим шумовой комбинации 0100000. Используя это обстоятельство и формулу (VII.2.24), получим все элементы второго класса смежности. Контрольные числа, определяющие классы смежности с номерами от восьмого и больше, не содержатся в контрольной матрице, каждое из них представлено в виде некоторой суммы ее строк. (Это верно хотя бы уже потому, что (VII.2.26) содержит единичную подматрицу.) Например, контрольное число 1100 можно получить сложением четвертой и пятой строк или в результате суммирования первой и последней строк. Первая ситуация соответствует случаю одновременного искажения первого и второго проверочных символов , а вторая — случаю одновременного искажения первого информационного и последнего проверочного символа . Выбирая любую из указанных шумовых комбинаций и складывая ее с каждой из комбинаций кода, найдем все элементы восьмого класса смежности и т. д.

В коде (VII.2.25) , поэтому имеется возможность корректировать различных искажений символов его комбинаций, например искажений, вызванных 7 одиночными, 7 двойными и I тройной ошибкой (семь классов смежности табл. VII.1 содержат комбинации веса один, восемь — веса два, и один, а именно три и больше). При этом вероятность правильного приема комбинации кода в случае симметричного канала без памяти равна

(VII.2.29)

Если символы комбинации искажаются помехами не независимо, то среди векторов Е веса два наиболее вероятными оказываются вектора вида

(VII.2.30)

Они порождают так называемые двойные смежные (парные) ошибки. Естественно, что такого рода ошибки желательно включить в число корректируемых. Однако применительно к коду (VII.2.25) этого сделать нельзя, ибо комбинации 0001100 и 0110000 принадлежат одному (восьмому) классу смежности.

Изменим в (VII.2.25) порядок следования линейных форм, определяющих проверочные символы:

(VII.2.31)

Таблица VII.2

Таблица VII.3

Все контрольные числа и соответствующие им комбинации классов смежности этого кода представлены в табл. (VII.2.

Первые две строки контрольной матрицы этого кода отличаются от соответствующих строк (VII.2.26). контрольные числа, определяющие первый и второй класс смежности табл. VII.1 и VII.2. Код (VII.2.31), как и код (VII.2.25), позволяет корректировать 7 одиночных, 7 двойных и 1 тройную ошибку. Однако все комбинации вида (VII.2.30) в табл. VII.2. располагаются в разных смежных классах, и, следовательно, в число исправляемых двойных ошибок могут быть включены все парные ошибки. Таким образом, простой перестановкой линейных форм получен код с новым качеством, корректирующий помимо всех одиночных ошибок все двойные смежные ошибки. Наконец, рассмотрим еще один семизначный бинарный код с тремя информационными символами:

(VII.2.32)

Все контрольные числа и определяемые ими классы смежности представлены в табл. VII.3: 7 из них содержат комбинации веса один и 8— веса два, а кодовое расстояние , что на единицу меньше, чем в двух предыдущих кодах. Однако несмотря на последнее обстоятельство, код (VII.2.32) в случае бинарного симметричного канала обеспечивает большую вероятность правильного приема комбинации, ибо имеется возможность исправить в ней, кроме всех одиночных, 8 двойных ошибок (а не 7 двойных и одну тройную, как было ранее). Вероятность правильного приема

(VII.2.33)

Разница между этой величиной и (VII.2.29), конечно, очень мала, и отмеченный факт имеет лишь принципиальное значение — он является хорошей иллюстрацией положения, согласно которому оптимизация кода в смысле максимума d еще не означает оптимизацию в смысле максимума вероятности правильного приема.

В работе [36] приведена таблица бинарных кодов, обеспечивающих максимум вероятности правильного приема комбинации в случае двоичного симметричного канала без памяти. Эта таблица была составлена Удаловым А. П. и Супруном Б. А. главным образом на основе работ [29, 53, 54, 160-162, 165].