Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Если при использовании этого кода принята последовательность у = 010011, то S = у Я = 110. Согласно приведенной таблице z = 001000 и наиболее вероятное кодовое слово равно х = y@z = = 011011. Поэтому декодированным сообщением будет 011.
Из дальнейшего ясно, что приведенное в таблице множество шумовых последовательностей точно совпадает с множеством ошибок, которые будут исправлены (независимо от переданного кодового слова). В тех случаях, когда в канале появляется любая из этих шумовых
217
Синдром
Шумовая
последова'
тельность
Проверочная
матрица
S
г
н
000 011 101 110 100 010
001 111
000000
100000
010000
001000
000100
000010
000001
100100
011
101
110
100
010
001
Рис. 6.1.4. Таблица декодирования для кода, приведенного на рис. 6.1.1.
последовательностей, декодер вычисляет соответствующий синдром и отыскивает в таблице декодирования эту самую шумовую последовательность. В тех случаях, когда появляется шумовая последовательность, не содержащаяся в таблице, декодер выбирает по таблице некоторую шумовую последовательность, и результат декодирования получается ошибочным. Для кода, представленного на рис. 6.1.1, и для декодирующей таблицы, представленной на рис. 6.1.4, исправляются все единичные ошибки, а также одна из двойных ошибок. Синдром 111 в таблице на рис. 6.1.4 имеет несколько конфигураций двойных ошибок, однако в таблицу может быть включена лишь одна из них; совершенно ясно, что в случае двоичного симметричного канала безразлично, какую из них включать.
Рассуждая подобным образом, можно убедиться, что для систематического кода с проверкой на четность, использующего таблицу декодирования, вероятность ошибочного декодирования в двоичном симметричном канале равна вероятности появления шумовой последовательности, не включенной в таблицу. Поскольку в таблице на рис. 6.1.4 содержатся одна безошибочная последовательность, шесть последовательностей, содержащих единичные ошибки, и одна последовательность, содержащая двойную ошибку, то вероятность ошибки для этого случая дается соотношением
Как было выяснено, синдром, соответствующий шумовой последовательности z, определяется соотношением S = гН. Если z содержит лишь одну ошибку, скажем на п-й позиции, то z# совпадает с п-й строкой матрицы Я. Если все строки матрицы Я ненулевые и различные, то безошибочная последовательность и все последовательности, содержащие единичные ошибки, имеют различные синдромы и поэтому код может исправлять все единичные ошибки. Для кодов с N—L проверочными символами существует 2N~L — 1 различных ненулевых последовательностей, которые могут быть выбраны в качестве
Ре — 1 — (1—е)6 — 6(1 — е)5е — (1—е)4е2. (6.1.15)
Коды Хэмминга
21?
N
L
Oil
101
110
Ul
100
010
001
3
7
15
31
26
Набор значений N, L для кодов Хэмминга
Проверочная матрица для
N = 7, А= 4
Рис. 6.1.5.
строк матрицы Я; поэтому при N ^ 2N~L — 1 строки Я можно выбирать ненулевыми и различными.
Коды Хэмминга — это коды, для которых строки матрицы Я различны и включают все ненулевые последовательности длины N—L. Поэтому ясно, что для таких кодов N и L связаны соотношением
На рис. 6.1.5 приведены небольшая таблица значений N и L, удовлетворяющих соотношению (6.1.15), и матрица Я для случая
Так как таблица декодирования для кодов Хэмминга не содержит ничего, кроме безошибочной последовательности и всех последовательностей с единичными ошибками, то ясно, что любая возможная принятая последовательность является либо кодовым словом, либо лежит на расстоянии 1 от одного и только от одного из кодовых слов.
Эти коды являются примером сферически упакованных кодов. Сферой радиуса е вокруг некоторой последовательности назовем множество всех последовательностей, лежащих на расстоянии е или меньшем от этой последовательности. Сферически упакованным кодом с исправляющей способностью е назовем код, у которого сферы радиуса е вокруг кодовых слов взаимно не пересекаются и любая последовательность лежит на расстоянии, не большем е + 1 от какого-либо кодового слова. При декодировании принятой последовательности в ближайшее кодовое слово исправляются все конфигурации не более чем е ошибок и некоторые конфигурации е + 1 ошибок; ни одна из конфигураций большего числа ошибок не исправляется. Легко видеть (см. § 5.8), что для двоичного симметричного канала сферически упакованный код с такой схемой декодирования обладает минимальной вероятностью ошибки среди всех кодов с той же самой длиной блока и с тем же самым числом кодовых слов.
