Тема: Методы построения блочных корректирующих кодов.

План лекции.

1. Коды, построенные на основе увеличения кодового расстояния.

2. Коды, построенные на основе проверки на четность.

3. Коды, построенные на основе защиты сдвоенными элементами.

Коды, построенные на основе увеличения кодового расстояния

Идея обнаружения и исправления ошибок в таких кодах заключается в следующем. Для передачи символов сообщения используют не все N возможных комбинаций элементов символов кода длиной n, а только часть из них N₀,которые называются разрешенными символами кода. Оставшиеся ΔN комбинаций (ΔN = N – N₀)называют запрещенными. Ошибка обнаруживается тогда, когда приемник получает запрещенную комбинацию элементов символов кода. Всякий код, у которого  ΔN > 0, способен обнаруживать ошибки в ΔN случаях из N. Доля обнаруживаемых ошибок (s) определяется выражением:

.

По формуле (15.2) легко определить избыточность такого корректирующего кода (R_k ):

,

где H(N₀) – энтропия кода с объемом алфавита N₀;

H(N) – энтропия кода с объемом алфавита N;

N – число элементов в кодовом символе;

m_k – основание кода.

Исправление ошибок в корректирующих кодах заключается в том, что, обнаружив ошибку, определяют кодовое состояние от полученной запрещенной комбинации k_i до всех разрешенных символов кода k_j (j=1, 2, ..., N₀) и в качестве переданного символа кода считается тот из разрешенных символов кода, до которого расстояние минимально. Таким образом, исправление ошибок корректирующими кодами производится с помощью трех последовательных операций:

− определения кодового расстояния между принятой кодовой комбинацией и разрешенными кодовыми символами;

− отыскания минимального кодового расстояния;

− присвоение принятой кодовой комбинации значения ближайшего к ней (по кодовому расстоянию) разрешенного кодового символа.

Например, в трехзначном равномерном двоичном коде число возможных кодовых комбинаций 8:

 000, 001, 010, 011, 100, 101, 010, 111,

кодовое расстояние между которыми (d_ij) равно 1. Ошибка в любом одном элементе символа кода превращает передаваемый разрешенный кодовый символ в другой, но так же разрешенный.

Если увеличить кодовое расстояние (d_ij = 2), то есть сделать разрешенными кодовые символы отличающимися в двух элементах (001, 111, 010, 100), то помехозащищенность кода увеличивается. Действительно, если в процессе передачи возникает ошибка только в одном элементе любого разрешенного символа, то эта комбинация превращается в запрещенную, что свидетельствует о появлении одиночной ошибки в символе кода, хотя и неизвестно, какой именно. Такой код не позволяет выяснить, какой конкретно из передаваемых элементов искажен, а значит и не позволяет исправить ошибку.

Если еще больше увеличить кодовое расстояние (d_ij = 3), т. е. сделать разрешенными кодовые символы отличными друг от друга в трех элементах (напри­мер, 111, 000), то помехозащищенность кода еще более возрастает.

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

Из приведенного примера видно, что для обнаружения единичной ошибки в символе кода требуется один избыточный элемент в символах кода, чтобы обеспечить минимальное кодовое расстояние (расстояние d_ij между разрешенными символами), равное 2, а для исправления в символах кода одной ошибки необходимо увеличить минимальное кодовое расстояние между символами кода (d_ij) до 3, то есть ввести в символы кода два избыточных элемента. В общем случае для избыточных кодов справедливо соотношение:

d_ij = 1 + p + q ,

где p ≥  q;

p – количество обнаруживаемых ошибок в символах;

q – количество исправляемых ошибок в символах кода.

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

Таблица 16.1

Характеристика кодов			Свойства кодов
d	p	q
1	0	0	Отличает одну кодовую комбинацию от другой.
2	1	0	Обнаруживает одну ошибку.
3	1	1	Обнаруживает и исправляет одну ошибку.
	2	0	Обнаруживает две ошибки.
4	2	1	Обнаруживает две ошибки и исправляет одну.
	3	0	Обнаруживает три ошибки.
5   Дата добавления: 2018-05-12; просмотров: 367; Мы поможем в написании вашей работы! Поделиться с друзьями: ⇐ Предыдущая567891011121314Следующая ⇒ Мы поможем в написании ваших работ! . . © 2014-2024 — Студопедия.Нет — Информационный студенческий ресурс. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав (0.015)