Основные виды избыточных помехоустойчивых кодов.

Основные виды избыточных помехоустойчивых кодов

Оглавление

Код с повторением

Этот код имеет избыточность R = (k+k)/k = 2 и минимальное кодовое расстояние d = 2, так как обнаруживаются одиночные ошибки и не обнаруживаются двойные ошибки в парных разрядах. Число двойных необнаруживаемых ошибок равно k, и поэтому вероятность необнаружения ошибки (или вероятность перерождения кодовой комбинации) при независимых ошибках приближенно равна kq²(1 - q)^2k-2 ~ kq².

Код с четным числом единиц

Этот код образуется путем добавления к каждой k - разрядной комбинации одного элемента, такого, что в k+1 разрядной комбинации число единиц четное. Избыточность кода:

R = (k+1)/k = 2.

При искажении двух элементов получается комбинация с четным числом единиц, т.е. кодовая, и ошибка не обнаруживается. Значит, d = 2. Вероятность необнаружения приближенно равна

i²_k+1q²(1 - q)^k-1 ~ (k + 1)^kq²/2. Отсюда видно, что добавление всего одного разряда значительно повышает помехозащищенность кодовых комбинаций (для безызбыточного кода вероятность необнаружения приблизительно равна kq).

Код с постоянным числом единиц

Код образует кодовые комбинации с заданным числом единиц (а значит - и нулей). Его особенностью является то, что в нем не разделяются информационные и дополнительные разряды. Такой код называется неразделимым. Число кодовых комбинаций рассматриваемого кода зависит от числа единиц. Оно максимально при равенстве единиц и нулей и равно C^n/2_n. Избыточность кода равна R = n/ LogC^n/2_n, она падает с ростом n. Оценим корректирующую способность. Кодовая комбинация не обнаруживается, если 0 переродится в 1 и 1 - в 0. Отсюда d = 2, а вероятность необнаружения приближенно равна (n/2)²q².

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

Линейные коды

Линейными называются коды, в которых проверочные элементы определяются как сумма по mod2 совокупностей информационных элементов. По-видимому, меняя совокупности информационных элементов (их число и состав), определяющих проверочные элементы, можно получать различные корректирующие коды. Примером линейного кода может служить 8-элементный код, образованный кодовыми комбинациями a₃a₂a₁a₀b₃b₂b₁b₀, в которых проверочные элементы b_i зависят от информационных следующим образом: b₀ = a₀ + a₁ + a₂,
b₁ = a₀ + a₁ + a₃,
b₂ = a₀ + a₂ + a₃,
b₃ = a₁ + a₂ + a₃. Для упомянутого кода на приемной стороне опознаватели одиночных ошибок формируются следующим образом: F₀ = b₀ + a₀ + a₁ + a₂,
F₁ = b₁ + a₀ + a₁ + a₃,
F₂ = b₂ + a₀ + a₂ + a₃,
F₃ = b₃ + a₁ + a₂ + a₃. Равенство опознавателя нулю свидетельствует об отсутствии ошибок.

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

Коды Хэмминга

К кодам Хэмминга относят линейные разделимые коды с минимальным кодовым расстоянием 3 и 4, проверочные элементы которых определяются по принципу проверки на четность для определенных групп информационных элементов. Коды с такими расстояниями d позволяют исправить одиночные ошибки или исправить одиночные и обнаруживать двойные ошибки.
Хемминг впервые построил код с исправлением одиночных ошибок, опознаватели (синдромы) которых являются двоичной записью номера искаженного элемента, т.е. при отсутствии ошибки опознаватель равен ...0000, при искажении первого элемента - ...0001, при искажении второго элемента - ...0010, при искажении третьего элемента - ...0011 и т.д.

Циклические коды

Циклические коды мы подробно рассмотрим в следующей главе.

Предыдущий

Следующий