Научная литература
booksshare.net -> Добавить материал -> Математика -> Аршинов М.Н. -> "Коды и математика (рассказы о кодировании) " -> 23

Коды и математика (рассказы о кодировании) - Аршинов М.Н.

Аршинов М.Н., Садовский Л.Е. Коды и математика (рассказы о кодировании) — М.: Наука, 1983. — 144 c.
Скачать (прямая ссылка): kodiimatematika1983.pdf
Предыдущая << 1 .. 17 18 19 20 21 22 < 23 > 24 25 26 27 28 29 .. 50 >> Следующая


Алгоритм исправления одиночных ошибок в этом случае удивительно прост. Если вектор U содержит ошибочный символ в і-й позиции, то синдром S(и) этого вектора совпадает с і-м столбцом проверочной .матрицы. Таким образом, этот синдром, читаемый как двоичное число, и есть номер ошибочного символа.

Код Хемминга и в общем случае допускает усовершенствование того же рода, что и (7,4)-код из § 9. Добавление проверочного символа а0, осуществляющего общую проверку на четность, приводит, как и там, к расширенному коду Хемминга с дополнительной способностью обнаруживать двойные ошибки, Его проверочная матрица легко может

( быть получена нз матрицы кода Хемминга: к каждой строке последней следует впереди приписать нулевой символ, а к получившимся строкам — строку из единиц, соответствующую общей проверке на четность:

Например, из приведенной выше проверочной матрицы для (15,11)-кода Хемминга получается следующая проверочная матрица для расширенного (16,11)-кода:

/1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\ /000000001 1 1 1 I 1 1 1\ 0000111100001111 \001 1001 1001 1001 1/ \о 10101010 І0І01П1/

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

В первом случае считаем, что произошла одиночная ошибка, и ее положение определяется номером столбца, с которым совпадает синдром.

Во втором случае считаем, что допущены две или любое большее четное число ошибок, если S (и) Ф 0. Если же S(U)=0, то, как обычно, полагаем, что ошибок при передаче не было.

Задачи и дополнения

1. Построить таблицу синдромов и соответствующих

2. Доказать, что алгоритм синдромного декодирования позволяет

исправить любое количество ошибок, не превосходящее , где

Указание. Достаточно проверить, что все векторы веса

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

«o+ai+aa+. . .+ocfi=O.

лидеров для (7,3)-кода с порождающей матрицей

d —кодовое расстояние.

,64 3. Код с проверочной матрицей

/ 1 0 1 0 0 0 0\ I 1 1 0 1 0 0 0 \ Я= 0 10 0 10 0]

\oooooio/ \0 0 0 0 0 0 1/

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

4. Проверить, что для обычного (нерасширенного) кода Хемминга лидеры ненулевых смежных классов исчерпываются всеми векторами веса 1. Верно ли это для расширенного кода Хемминга?

13. О КОДАХ, ИСПРАВЛЯЮЩИХ

НЕСИММЕТРИЧНЫЕ ОШИБКИ

На практике нередко встречаются каналы, отличающиеся асимметричным характером ошибок, скажем, такие, в которых преобладают замещения вида 0 ->• 1 (т. е. вместо нуля принимается единица), а замещения 1 -> 0 крайне редки.

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

Исходное соображение здесь очень простое: если в канале невозможны ошибки вида 1 -»- 0, то в принятом двоичном слове нет нужды проверять позиции с нулевыми символами — они наверняка переданы без искажений. Будем поэтому производить проверку таким образом, чтобы ее результат зависел только от позиций с единичными символами, точнее, от номеров этих позиций. С этой целью для произвольного двоичного слова U=XiXi...хп составим сумму

S(U)=ZxiL (1)

1 = 1

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

Как обычно, постараемся найти простое условие, выделяющее кодовые слова среди прочих. Будем искать это ус-

3 М. Н. Аршинов, Л. Е. Садовский

65 лсбиє в виде сравнения по некоторому модулю I. Представим себе, что число / уже выбрано, и рассмотрим код, состоящий из всех таких слов V = X1 X2 ... Xn, для которых

S(W)=0 (mod /), (2)

т. е. из слов, для которых сумма номеров единичных позиций делится на I без остатка. Обозначим указанный код через Vn, і- Так, при п=4, /=5 получим следующее множество кодовых слов:

V4 6= {0000, 100], 0110, 1111}.

Нетрудно убедиться, хотя бы перебором всех возможных случаев, что данный код исправляет любые одиночные ошибки вида 0->¦ 1. Например, ошибка в третьем символе слова 1001 переводит его в слово 1011. При этом никакое другое кодовое слово не могло преобразоваться в результате одиночной ошибки в слово 1011. Поэтому получатель декодирует слово 1011 однозначно, считая, что было послано слово 1001. Аналогично обстоит дело с другими двоичными наборами, содержащими одиночные замещения нуля на единицу. Отметим, что в некоторых случаях (но не всегда!) возможно исправление также и двойных замещений нуля на единицу. Один из таких случаев ¦— ошибка в двух первых символах слова 0000. Получающееся при этом слово 1100 не является кодовым и не могло получиться ни из какого кодового слова в результате одиночной ошибки. К тому же имеется единственный вариант двойного замещения, переводящего кодовое слово в слово 1100,— именно тот, который был указан выше.
Предыдущая << 1 .. 17 18 19 20 21 22 < 23 > 24 25 26 27 28 29 .. 50 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed