Основы теории принятая статистических решений 1051 32 страница

Таблица 6.3. Предел возможностей коррекции для кода (127,106)

Количество битовых ошибок	Количество необходимых классов смежности	Общее число необходимых классов смежности

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

1. Для получения нетривиального соотношения между исправлением и обнаруже­нием ошибок желательно, чтобы код имел возможности коррекции ошибок, по крайней мере, с? = 2. Согласно уравнению (6.44), минимальное расстояние при этом равно = 2t + 1 = 5.

2. Чтобы кодовая система была нетривиальной, желательно, чтобы количество бит данных было не менее к = 2. Следовательно, число кодовых слов 2* = 4. Далее бу­дем считать наш код следующим: (п, 2).

3. Нас интересует минимальное значение п, которое позволит исправлять все одно- и двухбитовые ошибки. В этом примере каждый из 2" н-кортежсй в матрице будет та­булирован. Минимальное значение п нас интересует потому, что при каждом увели­чении п на единицу число /г-кортежей в нормальной матрице удваивается. Это усло­вие, разумеется, диктуется только соображениями удобства использования таблицы. Для реальных прикладных кодов минимальное значение п выбирается по разным причинам — эффективность использования полосы пропускания и простота систе­мы. Если при выборе п используется предел Хэмминга, то п следует выбрать равным

7. В то же время размерность полученного кода (7,2) не соответствует указанным выше требованиям г = 2 и d_nm = 5. Чтобы увидеть это, следует ввести другую верхнюю границу возможностей кода в коррекции г-битовых ошибок (или d_mn). Эта граница, называемая предел Плоткина [7], определяется следующим образом:

d_mn<ⁿ\^2k ' • (6.54)

2 -1

В общем случае, линейный код (л, к) должен удовлетворять всем перечисленным вы­ше условиям, включая возможности коррекции ошибок (или минимальное расстояние). Для высокоскоростных кодов из удовлетворения предела Хэмминга следует удовлетво­рение предела Плоткина; это справедливо, например, для рассмотренного ранее кода (127,106). Для кодов с низкими скоростями передачи существует обходной путь удовле­творения названных требований [7]. Поскольку в нашем примере речь идет именно о таких кодах, важно оценить их возможности в коррекции ошибок с помощью предела Плоткина. Поскольку d_nm = 5, из уравнения (6.53) получаем, что л должно быть равно 8; следовательно, для удовлетворения всех требований, поставленных в этом примере, ми­нимальная размерность кода равна (8,2). Можно ли практически использовать подоб­ный код (8, 2)? Этого делать не стоит, поскольку это потребует слишком большой поло­сы пропускания; лучше выбрать более эффективный код. Данный код мы используем здесь только с методической целью, единственным его преимуществом являются удоб­ные размеры его нормальной матрицы.

6.6.3. Разработка кода (8, 2)

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

1. Количество кодовых слов 2* = 2² = 4.

2. Среди кодовых слов должен быть нулевой вектор.

3. Следует учесть свойство замкнутости — сумма двух любых кодовых слов в про­странстве должна давать кодовое слово из этого же пространства.

4. Каждое кодовое слово содержит 8 двоичных разрядов.

5. Поскольку d_am = 5, весовой коэффициент каждого кодового слова (за исключением нулевого) также должен быть не менее 5 (в силу свойства замкнутости). Весовой ко­эффициент вектора определяется как число ненулевых компонентов этого вектора.

6. Предположим, что код является систематическим; значит, 2 крайних правых би­та каждого кодового слова являются соответствующими битами сообщения.

Далее предлагается вариант набора кодовых слов, удовлетворяющих всем перечислен­ным выше требованиям.

Сообщения Кодовые слова

0 00000000

01 11110001

10 00111110

И 11001111

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

6.6.4. Соотношение между обнаружением и исправлением ошибок

Для кодовой системы (8, 2), выбранной в предыдущем разделе, матрицу генератора (кхп) = (2 х 8) можно записать в следующем виде:

'О 0 1 1 1 1 1 01

G =

1 1 1 1 0 0 0 1

Декодирование начинается с расчета синдрома, что можно представлять как изучение “симптомов” ошибки. Для кода (л, к) (и - ^-битовый синдром S является произведе­нием принятого n-битового вектора г и транспонированной проверочной матрицы Н размерностью (п - к) х п. Проверочная матрица Н построена таким образом, что стро­ки матрицы G ортогональны строкам матрицы Н, т.е. GH^r = 0. В нашем примере кода (8,2) S — это 6-битовый вектор, а Н — матрица размером 6x8, где

Синдром для каждой модели ошибки можно рассчитать, исходя из уравнения (6.37), а именно

/= 1,.... 2^я-*,

где S, — один из 2"~* = 64 синдромов, ае, - один из 64 образующих элементов клас­сов смежности (моделей ошибки) в нормальной матрице. На рис. 6.15, помимо самой нормальной матрицы, показаны все 64 синдрома для кода (8, 2). Набор синдромов рассчитывался с помощью уравнения (6.37); позиции произвольной строки (смежный класс) нормальной матрицы имеют один и тот же синдром. Исправление искаженного кодового слова осуществляется путем расчета его синдрома и локализации моделей ошибки, соответствующей этому синдрому. В заключение модель ошибки прибавляет­ся (по модулю 2) к поврежденному кодовому слову, что и дает правильное кодовое слово. Из уравнения (6.49), повторно приведенного ниже, видно, что между возмож­ностями обнаружения и исправления ошибок существует некий компромисс, ограни­чиваемый расстоянием.

d_nm> СХ + Р+ 1

Здесь а представляет количество исправляемых битовых ошибок, а (3 — количество обнаруживаемых битовых ошибок, причем (3 > ос. В коде (8, 2) возможны следующие компромиссы между этими двумя величинами:

Обнаружение ((3) Исправление (ос)

~2 2

3 1

4 О

Из данной таблицы видно, что код (8, 2) можно использовать только для исправления ошибок; это означает, что код вначале обнаруживает |3 = 2 ошибки, после чего они исправляются. Если пожертвовать возможностью исправления и использовать код для исправления только однобитовых ошибок, то возможность обнаружения ошибки воз­растает до (3 = 3 ошибок. И наконец, если целиком отказаться от исправления ошибок, то декодер сможет обнаруживать ошибки с (3 = 4. В случае, если ошибки только обна­руживаются, реализация декодера будет очень простой: производится вычисление синдрома и обнаруживается ошибка при появлении любого ненулевого синдрома.

Для исправления однобитовых ошибок декодер может реализовываться с логиче­скими элементами [4], подобными приведенным на рис. 6.12, где принятый вектор кода г поступал в схему в двух точках. В верхней части рисунка принятые символы поступают на логический элемент исключающего ИЛИ, который и определяет син­дром. Для любого принятого вектора синдром рассчитывается согласно уравне­нию (6.35).

S, = г,Н^г 1=1,...,2"-*

	1.
	2.
	3.
	5.
	6.
	7.
	8.
	9.
	10.
	13.
	14.
	15.
	16.
	17.
	18.
	19.
	20.
	21.
	22.
	23.
	24.
	25.
	26.
	27.
	28.
	29.
	30.
	31.
001100.	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.
101001 '	57.
100111 *	58.
	59.
	60.
	61.
	62.
	63.
	64.

С помощью значений Н⁷ для кода (8, 2), необходимо так соединить элементы схемы (подобно тому, как это было сделано на рис. 6.12), чтобы вычислялось следующее:

Каждая из цифр Sj (j= 1,..., 6), определяющая синдром S, (/= 1,..., 64), связана с вход­ным принятым вектором кода следующим образом:

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

. Если декодер реализован так, чтобы исправлять только однобитовые ошибки (т.е. а= 1 и Р = 3), это эквивалентно ограничению матрицы на рис. 6.15 девятью первыми классами смежности, а исправление ошибок происходит, только когда один из восьми синдромов соответствует появлению однобитовой ошибки. Затем схема декодирова­ния (подобная изображенной на рис. 6.12) преобразует синдром в соответствующую модель ошибки. Далее модель ошибки прибавляется по модулю 2 к “потенциально” искаженному принятому вектору, т.е. происходит исправление ошибки. Для проверки ситуаций, когда синдром не равен нулю, а схемы коррекции нет, нужно вводить до­полнительные логические элементы (например, для однобитовых ошибок, соответст­вующих синдромам 10-64).

Если декодер реализован так, чтобы исправлять одно- и двухбитовые ошибки (а это оз­начает, что обнаруживается, а затем исправляется р = 2 ошибки), это эквивалентно ограни­чению матрицы (рис. 6.15) 37 классом смежности. Хотя код (8,2) может исправлять неко­торые модели трехбитовых ошибок, соответствующие образующим элементам классов смежности под номерами 38—64, декодер чаще всего реализуется как декодер с ограничен­ным расстоянием', это означает, что он исправляет все искаженные символы, содержащие ошибку только в t или меньшем числе бит. Нереализованные возможности используются для некоторого улучшения процесса обнаружения ошибок. Как и ранее, реализация деко­дера подобна схеме, изображенной на рис. 6.12.

6.6.5. Взгляд на код сквозь нормальную матрицу

В контексте рис. 6.15 код (8,2) удовлетворяет пределу Хэмминга. Иными словами, из нормальной матрицы можно видеть, что код (8,2) способен исправлять все модели одно- и двухбитовых ошибок. Рассмотрим следующее: пусть передача происходит по
каналу, который всегда вносит ошибки в виде пакета 3-битовых ошибок, и, следова­тельно, нет необходимости в исправлении одно- или двухбитовых ошибок. Можно ли настроить образующие элементы классов смежности так, чтобы они соответствовали только трехбитовым ошибкам? Нетрудно определить, что в последовательности из 8

бит существует

возможностей произвести трехбитовую ошибку. Если единст-

венным нашим желанием является коррекция только этих 56 моделей трехбитовых ошибок, то кажется, что в нормальной матрице достаточно места (достаточное коли­чество классов смежности), поскольку всего в ней имеется 64 строки. Будет ли это ра­ботать? Однозначно, нет. Для любого кода главным параметром, определяющим спо­собности кода к коррекции ошибок, является d_mm. Для кода (8, 2) d_nm = 5, а это означа­ет, что возможно исправление только 2-битовых ошибок.

Как нормальная матрица может помочь разобраться, почему эта схема не будет рабо­тать? Чтобы осуществить исправление ^-битовых ошибок для группы ^-битовых моделей ошибки, полная группа векторов с весовым коэффициентом х должна быть классом смеж­ности, т.е. они должны находиться только в крайнем левом столбце. На рис. 6.15 можно видеть, что все векторы с весовым коэффициентом 1 и 2 находятся в крайнем левом столбце нормальной матрицы и нигде более. Если мы даже и втиснем все векторы с весо­вым коэффициентом 3 в строку со второго номера по 57-й, увидим, что некоторые из этих векторов снова появятся в матрице где-нибудь еще (что нарушит основное свойство нор­мальной матрицы). На рис. 6.15 затененные блоки обозначают те 56 векторов, которые имеют весовой коэффициент 3. Взгляните на образующие элементы классов смежности, представляющие 3-битовые модели ошибки, в строках 38, 41—43, 46-49 и 52 нормальной матрицы. Потом посмотрите на позиции в тех же строках в крайнем правом столбце, где затененные блоки показывают другие векторы с весовым коэффициентом 3. Видите неко­торую неопределенность, существующую для каждой строки, о которых говорилось выше, и понятно ли теперь, почему нельзя исправить все 3-битовые модели ошибки с помощью кода (8,2)? Допустим, декодер принял вектор с весовым коэффициентом 3 — 11001000, размещенный в строке 38 в крайнем правом столбце. Это искаженное кодовое слово могло появиться, во-первых, при передаче кодового слова 11001111, искаженного 3-битовой модели ошибки 00000111, а во-вторых, при передаче кодового слова 00000000, ис­каженного 3-битовой моделью ошибки 1 1001000.

6.7. Циклические коды

Важным подклассом линейных блочных кодов являются двоичные циклические коды (cyclic codes). Код легко реализуется на регистре сдвига с обратной связью; на подоб­ных регистрах сдвига с обратной связью вычисляется синдром; алгебраическая струк­тура циклического кода естественным образом позволяет эффективно реализовать ме­тоды декодирования. Итак, линейный код (п, к) называется циклическим, если он обла­дает следующим свойством. Если л-кортеж U= (и₀, и_х, и₂,..., и„~\) является кодовым словом в подпространстве S, тогда U(l)= (ы„__ь м₀, и_ь и₂,..., и„.₂), полученный из U с помощью циклического сдвига, также является кодовым словом в S. Или, вообще, U(i) = (M„_„ и„_,_{+ 1},..., и₀, и 1,..., ы_я_,_i), полученный i циклическими сдвигами, яв­ляется кодовым словом в S.

Компоненты кодового слова U = (и₀, и_ь и₂, ■■■, и_п_₍) можно рассматривать-как коэф­фициенты полинома U(X):

U(X) ⁼ Uq + U[X + и₂Х +... + и_п ~ 1Х^п. (6.54)

Полиномиальную функцию U(Xj можно рассматривать как “заполнитель” разрядов кодо­вого слова U, т.е. вектор л-кортежа описывается полиномом степени п -1 или меньше. Наличие или отсутствие каких-либо членов в полиноме означает наличие 1 или 0 в соот­ветствующем месте л-кортежа. Если,-й компонент отличен от нуля, порядок полинома равен л-1. Удобство такого полиномиального представления кодового слова станет более понятным по мере дальнейшего обсуждения алгебраических свойств циклических кодов.

6.7.1. Алгебраическая структура циклических кодов

В кодовых словах, выраженных в полиномиальной форме, циклическая природа кода проявляется следующим образом. Если U(X) является.кодовым словом, представлен­ным полиномом порядка (л - 1), то U⁰⁾(X) — остаток от деления Х'и(А") на Х"+ 1 — также является кодовым словом.

Иными словами,

_{= +} (6.55,а)

Х^п+1 Х^п+1

или, умножая обе части уравнения на Х"+ 1,

X'U(X) = q(X)(Xⁿ + 1) + U⁽⁰(X), (6.55,6)

остаток

что в модульной арифметике можно описать следующим образом:

и⁽⁰(Х) = Х'ида по модулю (X" + 1). (6.56)

Здесь “х по модулю у” означает остаток от деления х на у. Ниже справедливость вы­ражения (6.56) демонстрируется для случая < = 1.

l)(Xj = u₀ + u_lX+u₂X² +... + u_n-₂Xⁿ~²+u_n__iXⁿ~^l

XU(X)⁼ i/qX + U\X" + u₂X^ +... + u_n _₂Xⁿ *+ u_n _ iXⁿ

К последнему выражению прибавим и вычтем ы„_! или, поскольку мы пользуемся арифметическими операциями по модулю 2, можем прибавить, дважды.

XU(X) ~ | + UqX + и^Х“ + и₂Х^ Н 1-и_п_₂Х^{п 1} + и_п_= U^(X) + и_п^(Х^п +1)

U⁽¹>(X)

Поскольку порядок U⁽¹⁾(X) равен п - 1, этот полином не делится на X^я + 1. Таким обра­зом, используя уравнение (6.55,а), можно записать следующее:

U^X) = XV(X) по модулю (X^я + 1).

Обобщая, приходим к уравнению (6.56).

Пример 6.7. Циклический сдвиг вектора кода

Пусть U = 1 10 1 для п = 4. Выразите кодовое слово в полиномиальной форме и, используя уравнение (6.56), выполните третий циклический сдвиг кодового слова.

Решение

U(X) = 1 + X + X³ полином записан в порядке возрастания степени

X'U(X) = X³ + X⁴ + X⁶, где < = 3

Разделим ^ТДХ) на X⁴ + 1 и найдем остаток, используя полиномиальное деление.

X⁶ + X⁴ + X³

X^е + X²

X⁴ + X³ + X²

_______________ + 1

X³ + X² + I остаток U⁽³⁾(x)

Записываем остаток в порядке возрастания степеней: 1 + X² + X³, кодовое слово U® =10 11 представляет собой три циклических сдвига U = 1 10 1. Напомним, что для двоичных кодов операция сложения выполняется по модулю 2, так что + 1 = - 1, и, следовательно, в расче­тах знаки “минус” не отражены.

6.7.2. Свойства двоичного циклического кода

С помощью полиномиального генератора можно создать циклический код, почти так же как создавались блочные коды с использованием матрицы генератора. Полиномиальный гене­ратор g(X) для циклического кода (п, к) является единственным и имеет следующий вид:

g (X)=go + _glX + g₂X²+...+gyX^p. (6.57)

Здесь go и g_p должны быть равны 1. Каждый полином кодового слова в подпростран­стве имеет вид U(X) = m(X)g(X), где U(X) — полином степени п - 1 или меньше. Следо­вательно, полином сообщения ш(А') будет иметь следующий вид:

т(Х) =т₀ + т{Х + т₂Х² +... + /и„__р_₁Х"^_р_(6.58)

Всего в коде (п, к) существует 2^п~^р полинома кодовых слов и 2^к вектора кода. Поэтому на каждый вектор кода должен приходиться один полином кодового слова.

п-р = к

или

р = п — к

Отсюда следует, что g(X), как показано в уравнении (6.57), должен иметь степень п-к, и каждый полином кодового слова в коде (л, к) можно выразить следующим образом:

U(X) = (т₀ + т_уХ + т₂Х² +... + /Яп^Х"^-1) g(X). (6.59)

U будет считаться действительным кодовым словом из подпространства S тогда и только тогда, когда U(X) делится на g(X) без остатка.

Полиномиальный генератор g(X) циклического кода (л, к) является множителем X^й + 1, т.е. X" + 1 = g(X)h(X). Например,

X⁷ + 1 = (1 + X + X³) (1 + X + X² + X⁴).

Используя g(X) = 1 + X + X³ как полиномиальный генератор степени п-к = Ъ, можно полу­чить циклический код (л, к) = (7,4). Или же с помощью g(X) = 1 + X + X² + X⁴, где л - к=4, можно получить циклический код (7,3). Итак, если g(X) является полиномом степени л - к и множителем X" +1, то g(X) однозначным образом генерирует циклический код (л, к).

6.7.3. Кодирование в систематической форме

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

m(X) = т₀ = ni\X + т₂Х² +... + m_k _ jX* “ (6.60)

В систематической форме символы сообщения используются как часть кодового сло­ва. Мы можем сдвинуть символы сообщения в к крайних правых разряда кодового слова, а затем прибавить биты четности, разместив их в крайние левые л - к разряды. Таким образом, осуществляется алгебраическая манипуляция полинома сообщения, и он оказывается сдвинутым вправо на л - к позиций. Если теперь умножить т(Х) на Х"~^к, мы получим сдвинутый вправо полином сообщения:

Х^п-^кт(Х)=т₀Х^л~^к + т₁Х^п'^к+[ + -+т_к-Х~^[- (6.61)

Если далее разделить уравнение (6.61) на g(X), результат можно представить в сле­дующем виде:

X^я -*m(X) = q(X)g(X) + р(Х). (6.62)

Здесь остаток р(Х) записывается следующим образом:

р(Х)= р₀ +р_{Х +р₂Х^г +... + pn-k-iX" ^к '•

Также можно записать следующее:

р(Х) = X" ~*т(Х) по модулю g(X). (6.63)

Прибавляя р(Х) к обеим частям уравнения (6.62) и используя сложение по модулю 2, получаем следующее:

р(Х) + X" ' *т(Х) = q(X)g(X) - U(X). (6.64)

Левая часть уравнения (6.64) является действительным полиномом кодового слова, так как это полином степени л - 1 или менее, который при делении на g(X) дает нулевой остаток. Это кодовое слово можно записать через все члены полинома:

р(Х) + X” *т(Х) —р^ + р\Х + Р2Х² +... + Рл-к-iX” * ¹ + * + WjX” *^{+ 1} +... + иц^Х” *. Полином кодового слова соответствует вектору кода

и = {р₀, Pi,... Рп-к-1. '"О, ^т\' •••> ^тк-1) ■ (⁶-⁶⁵)

п-к к

бит четности бит сообщения

Пример 6.8. Циклический код в систематической форме

С помощью полиномиального генератора g(X) = 1 + X + X³ получите систематическое кодо­вое слово из набора кодовых слов (7, 4) для вектора сообщения m = 1 0 0 1 1.

---

Дата добавления: 2015-10-28