Совершенные и квазисовершенные коды.

⇐ ПредыдущаяСтр 14 из 18Следующая ⇒

Групповой (т, n ) код, исправляющий все ошибки веса, не большего k и никаких других, называется совершенным. Свойства совершенного кода:

1. Для совершенного (т, n )-кода, исправляющего все ошибки веса,

не большего к, выполняется соотношение . Верно и обратное утверждение:

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

3. Таблица декодирования совершенного кода, исправляющего все ошибки в не более чем к позициях, имеет в качестве лидеров все строки, содержащие не более к единиц. Верно и обратное утверждение.

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

Если т, n и k не удовлетворяют условию совершенности, то лучший групповой код, который им соответствует называется квазисовершенным, если он исправляет все ошибки кратности, не большей к, и некоторые ошибки кратности к + 1. Квазисовершенных кодов также очень мало.

Двоичный блочный ( m , n )-код называется оптимальным, если он минимизирует вероятность ошибочного декодирования. Совершенный или квазисовершенный код оптимален. Общий способ построения оптимальных кодов пока неизвестен.

Для любого целого положительного числа r существует совершенный ( m , n )- код исправляющий одну ошибку, называемый кодом Хэмминга (Hamming), в котором m =2 ^r - r -1и n =2 ^r -1.

Действительно,

Порядок построения кода Хэмминга следующий:

1. Выбираем целое положительное число r. Сообщения будут словами длины m =2 ^r - r – 1, а кодовые слова длины п = 2^r – 1;

2. В каждом кодовом слове b 1 b 2... b_n r бит с индексами - степенями двойки (2⁰, 2¹,..., 2^r^-1) являются контрольными, остальные в естественном порядке битами сообщения. Например, если r = 4, то биты b ₁ b ₂ b ₄ b ₈ контрольные, а b ₃ b ₅ b ₆ b ₇ b ₉ b ₁₀ b ₁₁ b ₁₂ b ₁₃ b ₁₄ b ₁₅ из исходного сообщения:

3.Строится матрица М из 2 ^r -1 строк и r столбцов. В i-ой строке стоят цифры двоичного представления числа i. Матрицы для r =2, 3 и 4 таковы:

4. Записывается система уравнений b М =0, где М- матрица из предыдущего пункта. Система состоит из r уравнений. Например, для

r=3:

5. Чтобы закодировать сообщение а₁ берутся в качестве bj , j не равно степени двойки, соответствующие биты сообщения и отыскиваются, используя полученную систему уравнений, те bj , для которых j степень двойки. В каждое уравнение входит только одно bj , j = 2 ⁱ . В выписанной системе b ₄ входит в 1-е уравнение, b ₂ во второе и b ₁ в третье. В рассмотренном примере сообщение а = 0111 будет закодировано кодовым словом b = 0001111.

Декодирование кода Хэмминга проходит по следующей схеме. Пусть принято слово b + е, где b переданное кодовое слово, а е строка ошибок. Так как b М = 0, то ( b + е) M = b М + e М = еМ. Если результат нулевой, как происходит при правильной передаче, считается, что ошибок не было. Если строка ошибок имеет единицу в i-й позиции, то результатом произведения еМ будет i-я строка матрицы М или двоичное представление числа i. В этом случае следует изменить символ в i-й позиции слова b + е , считая позиции слева, с единицы.

Пример. (4,7)-код Хэмминга имеет в качестве одного из кодовых слов b = 0001111. Матрица М_{7 3} приведена на шаге 3хода построения кода Хэмминга, Ясно, что b М = 0. Добавим к b строку ошибок е = 0010000. Тогда b + е = 0011111 и (b+ е)М = 011 = 3₁₀ т.е. ошибка находится в третьей позиции. Если e = 0000001, то b+ e = 0001110 и позиция ошибки (b+ e)М = 111 = 7₁₀ и т.п. Если ошибка допущена в более чем в одной позиции, то декодирование даст неверный результат.

Код Хэмминга - это групповой код.

Это следует из того, что ( m , n)-код Хэмминга можно получить матричным кодированием, при помощи т n - матрицы, в которой столбцы с номерами не степенями 2 образуют единичную подматрицу. Остальные столбцы соответствуют уравнениям шага 4 построения кода Хэмминга, т.е. 1-му столбцу соответствует уравнение для вычисления 1-го контрольного разряда, 2-му для 2-го, 4-му - для 4-го и т.д. Такая матрица будет при кодировании копировать биты сообщения в позиции не степени 2 кода и заполнять другие позиции кода согласно схеме кодирования Хэмминга.

Пример. Кодирующая матрица для (4,7)-кода Хэмминга

Ее столбцы с номерами 3, 5, 6и 7 образуют единичную подматрицу. Столбцы с номерами 1, 2 и 4 соответствуют уравнениям для вычисления контрольных бит, например, уравнению b ₁ = b ₃ + b ₅ + b ₇ соответствует столбец 1101, т.е. для вычисления первого контрольного разряда берутся 1, 2 и 4 биты исходного сообщения или биты 3,5 и 7 кода.

К ( m , n )-коду Хэмминга можно добавить проверку четности. Получится (т, n + 1) - код с наименьшим весом ненулевого кодового слова 4, способный исправлять одну и обнаруживать две ошибки.

Коды Хэмминга накладывают ограничения на длину слов сообщения: эта длина может быть только числами вида 2 ^r - r - 1: 1, 4, 11, 26, 57,.... Но в реальных системах информация передается байтам или машинными словами, т.е. порциями по 8, 16, 32или 64 бита, что делает использование совершенных кодов не всегда подходящим. Поэтому в таких случаях часто используются квазисовершенные ( m , n )-коды.

Квазисовершенные (т, n)-коды, исправляющие одну ошибку, строятся следующим образом. Выбирается минимальное n так, чтобы

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

Каждому из п разрядов присваивается слева-направо номер от 1 до n. Для заданного слова сообщения составляются к контрольных сумы S ₁ ,... Sk по модулю 2 значений специально выбранных разрядов кодового слова, которые помещаются в позиции-степени 2 в нем: для S ₁ (1 ≤ i ≤ к) выбираются разряды, содержащие биты исходного сообщения, двоичные числа-номера которых имеют в i-м разряде единицу. Для суммы S₁ это будут, например, разряды 3, 5, 7 и т.д., для суммы S₂ - 3, 6, 7 и т.д. Таким образом, для слова сообщения а = a ₁ … a_m будет построено кодовое слово b = S ₁ S ₂ a ₁ S ₃ a ₂ a ₃ a ₄ S ₄ a ₅ … a_m . Обозначим S сумму по модулю 2 разрядов полученного слова, соответствующих контрольной сумме S_i и самой этой контрольной суммы. Если S , то считается, что передача прошла без ошибок. В случае одинарной ошибки S будет равно двоичному числу-номеру сбойного бита. В случае ошибки, кратности большей 1, когда S > n ее можно обнаружить. Подобная схема декодирования не позволяет исправлять некоторые двойные ошибки, чего можно было бы достичь, используя схему декодирования с лидерами, но последняя значительно сложнее в реализации и дает незначительное улучшение качества кода.

Пример построения кодового слова квазисовершенного (9, n )-кода, исправляющего все однократные ошибки, для сообщения 100011010.

Искомое кодовое слово имеет вид

Далее нужно вычислить контрольные суммы

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

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

Совершенный код Хэмминга также можно строить по рассмотренной схеме, т.к. для него 2 ⁿ /( n + 1) = 2 ^m.

Для исправление одинарной ошибки к 8-разрядному коду достаточно приписать 4 разряда (2¹²/13 > 2⁸), к 16-разрядному 5, к 32-разрядному 6, к 64-разрядному 7.

Дата добавления: 2022-01-22; просмотров: 21; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 9 10 11 12 131415 16 17 18 Следующая ⇒

Мы поможем в написании ваших работ!