Совершенные и квазисовершенные коды.
Групповой (т, 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, а кодовые слова длины п = 2r – 1;
2. В каждом кодовом слове b 1 b 2... bn r бит с индексами - степенями двойки (20, 21 ,..., 2r-1) являются контрольными, остальные в естественном порядке битами сообщения. Например, если r = 4, то биты b 1 b 2 b 4 b 8 контрольные, а b 3 b 5 b 6 b 7 b 9 b 10 b 11 b 12 b 13 b 14 b 15 из исходного сообщения:
3.Строится матрица М из 2 r -1 строк и r столбцов. В i-ой строке стоят цифры двоичного представления числа i. Матрицы для r =2, 3 и 4 таковы:
4. Записывается система уравнений b М =0, где М- матрица из предыдущего пункта. Система состоит из r уравнений. Например, для
r=3:
5. Чтобы закодировать сообщение а1 берутся в качестве bj , j не равно степени двойки, соответствующие биты сообщения и отыскиваются, используя полученную систему уравнений, те bj , для которых j степень двойки. В каждое уравнение входит только одно bj , j = 2 i . В выписанной системе b 4 входит в 1-е уравнение, b 2 во второе и b 1 в третье. В рассмотренном примере сообщение а = 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 = 310 т.е. ошибка находится в третьей позиции. Если e = 0000001, то b+ e = 0001110 и позиция ошибки (b+ e)М = 111 = 710 и т.п. Если ошибка допущена в более чем в одной позиции, то декодирование даст неверный результат.
|
|
Код Хэмминга - это групповой код.
Это следует из того, что ( m , n)-код Хэмминга можно получить матричным кодированием, при помощи т n - матрицы, в которой столбцы с номерами не степенями 2 образуют единичную подматрицу. Остальные столбцы соответствуют уравнениям шага 4 построения кода Хэмминга, т.е. 1-му столбцу соответствует уравнение для вычисления 1-го контрольного разряда, 2-му для 2-го, 4-му - для 4-го и т.д. Такая матрица будет при кодировании копировать биты сообщения в позиции не степени 2 кода и заполнять другие позиции кода согласно схеме кодирования Хэмминга.
Пример. Кодирующая матрица для (4,7)-кода Хэмминга
Ее столбцы с номерами 3, 5, 6и 7 образуют единичную подматрицу. Столбцы с номерами 1, 2 и 4 соответствуют уравнениям для вычисления контрольных бит, например, уравнению b 1 = b 3 + b 5 + b 7 соответствует столбец 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 1 ,... Sk по модулю 2 значений специально выбранных разрядов кодового слова, которые помещаются в позиции-степени 2 в нем: для S 1 (1 ≤ i ≤ к) выбираются разряды, содержащие биты исходного сообщения, двоичные числа-номера которых имеют в i-м разряде единицу. Для суммы S1 это будут, например, разряды 3, 5, 7 и т.д., для суммы S2 - 3, 6, 7 и т.д. Таким образом, для слова сообщения а = a 1 … am будет построено кодовое слово b = S 1 S 2 a 1 S 3 a 2 a 3 a 4 S 4 a 5 … am . Обозначим S сумму по модулю 2 разрядов полученного слова, соответствующих контрольной сумме Si и самой этой контрольной суммы. Если S , то считается, что передача прошла без ошибок. В случае одинарной ошибки S будет равно двоичному числу-номеру сбойного бита. В случае ошибки, кратности большей 1, когда S > n ее можно обнаружить. Подобная схема декодирования не позволяет исправлять некоторые двойные ошибки, чего можно было бы достичь, используя схему декодирования с лидерами, но последняя значительно сложнее в реализации и дает незначительное улучшение качества кода.
Пример построения кодового слова квазисовершенного (9, n )-кода, исправляющего все однократные ошибки, для сообщения 100011010.
Искомое кодовое слово имеет вид
Далее нужно вычислить контрольные суммы
Таким образом, искомый код 0011000111010. Если в процессе передачи этого кода будет испорчен его пятый бит, то приемник получит код 0011100111010. Для его декодирования опять вычисляются контрольные суммы:
Приемник преобразует изменением пятого бита полученное сообщение в отправленное передатчиком, из которого затем отбрасыванием контрольных разрядов восстанавливает исходное сообщение.
Совершенный код Хэмминга также можно строить по рассмотренной схеме, т.к. для него 2 n /( n + 1) = 2 m.
Для исправление одинарной ошибки к 8-разрядному коду достаточно приписать 4 разряда (212/13 > 28), к 16-разрядному 5, к 32-разрядному 6, к 64-разрядному 7.
Дата добавления: 2022-01-22; просмотров: 21; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!