Построение кодов с заданной исправляющей способностью

До сих пор при рассмотрении корректирующих кодов мы предполагали заданной его значность n. Повышение корректирующей способности кода достигалось при сохранении n за счет уменьшения множества N разрешенных комбинаций (или уменьшения количества k информационных символов). Обычно же на практике коды строятся в обратном порядке: вначале выбирается количество информационных символов k, исходя из объема алфавита источника, а затем обеспечивается необходимая корректирующая способность кода за счет добавления избыточных символов.

Пусть известен объем алфавита источника N. Необходимое количество информационных символов определяется как наибольшее целое логарифма N:

,

Тогда N = 2 ^k.

Пусть также известно полное число ошибок Е, которое необходимо исправить.

Задача состоит в том, чтобы при заданных N и Е определить значность кода n, обладающего требуемыми корректирующими возможностями.

Полное число ошибочных комбинаций, подлежащих исправлению, равно Е · N = Е · 2 ^k. Так как количество запрещенных комбинаций равно N ₀ - N, то код обеспечивает исправление не более N ₀ - N комбинаций. Следовательно, необходимое условие для возможности исправления ошибок можно записать в виде:

N · E £ N ₀ - N,

где N ₀=2 ⁿ – полное число кодовых комбинаций значностью n.

Далее получим:

Или

(17.1)

Формула (17.1) выражает условие для выбора значности кода n.

Рассмотрим частные случаи. Если имеются ошибки разной кратности, то прежде всего необходимо обеспечить устранение однократных ошибок t = 1:

.

В этом случае зависимость (17.1) примет вид:

или

При построении кода целесообразно пользоваться таблицей 3.

Таблица 3

Соотношение между k и n для t=1

 

k
n

 

Если необходимо обеспечить устранение всех ошибок кратности от 1 до t, то нужно учесть, что:

- число возможных однократных ошибок ,

- число возможных двукратных ошибок ,

- число возможных t -кратных ошибок ,

- общее число ошибок .

При этом зависимость (1.1) примет вид:

 

(17.2)

 

Откуда следует:

 

.

 

Пусть t = 2, тогда полное число ошибок Е равно:

 

Е = .

 

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

 

.

 

При построении кода можно воспользоваться таблицей 4.

 

Таблица 4

Соотношение между k и n для t =2

k
n

 

Условие (17.2) является нижней оценкой для длины корректирующего кода, т. е. оно определяет необходимую минимальную длину кода n, обеспечивающую исправление ошибок заданной кратности при известном числе разрешенных комбинаций N или числе информационных символов k.

Это же условие является верхней оценкой для N или k, т. е. определяет максимально возможное число разрешенных комбинаций или информационных символов для кода длины n, обеспечивающего исправление ошибок заданной кратности.

 

Лекция 18. Кодирование информации систематическим кодом.

План:

1. Систематические коды

2. Код Хемминга