Классификация помехоустойчивых кодов

Помехоустойчивые коды делятся на блочные и непре­рывные. Блочные коды делятся на равномерные (каждому сообщению соответствует блок с постоянным числом символов (разрядов) n) и неравномерные (сообщениям соответствуют блоки с разным числом символов). Широкое практическое приме­нение нашли равномерные коды. К неравномерным кодам относитcя, например, код Морзе. К непрерывным кодам отно­сятся рекуррентные (называемые также сверточными). Они представ­ляют собой непрерывные последовательности единичных элемен­тов, не разделенные на блоки. В таких кодах избыточные разря­ды помещаются в определенном порядке между информацион­ными.

Равномерные блочные коды делятся на разделимые и неразде­лимые. В разделимых кодах элементы информационной и прове­рочной частей кодовой комбинации всегда стоят на определенных местах. В неразделимых кодах деление на информационные и про­верочные разряды отсутствует. К неразделимым кодам относятся коды с постоянным весом: например, рекомендованный МККТТ телеграф­ный код № 3 — семиразрядный код «3 из 7» с постоянным весом, равным 3 (весом кодовой комбинации называется число содержащихся в ней еди­ниц. Любая комбинация кода № 3 содержит три единицы: 1001010 или 0011001 и т. д.).

Разделимые коды в свою очередь делятся на систематические (линейные) и несистематические (нелинейные). Код называется линейным, если любая разрешенная кодовая комбинация может быть получена в результате линейной операции над набором k ненулевых линейно-независимых кодовых комбинаций. В система­тических кодах проверочные элементы формируются линейным преобразованием информационных. Эти коды в системах передачи данных получили наибольшее применение.

Нелинейные коды указанным свойством не обладают и применяются значительно реже. Примером несистематического ко­да является код с контрольным суммированием. В этом коде про­верочные разряды записываются в виде суммы единиц в кодовой комбинации (например, итеративный код).

Различают два метода формирования проверочной группы: поэлементный и в целом. Формирование проверочной группы в целом характерно для широко распространенных полиноминальных кодов (их разновидность – циклические коды). Среди систематических кодов большое применение на­шли коды Хэмминга с поэлементным формированием проверочной группы. Эти коды, обеспечивающие d₀=3 (встречается и d₀=4), позволяют исправить одну ошибку.

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

Классификация помехоустойчивых кодов приведена на рисунке:

Лекция 6 Коды Хэмминга Общие сведения

Коды Хэмминга относятся к линейным систематическим кодам с d₀=3 и d₀=4, в которых проверочные разряды формируются линейным преобразованием информационных разрядов. Правило нахождения проверочных разрядов является основной задачей корректирующих кодов.

Для кода Хэмминга это правило можно определить следующим образом: каждый элемент b_i проверочной части кодовой комбинации находится отдельно и определя­ется своим линейным оператором R_i. В формировании проверочного элемента b_i участвует определенный набор информационных символов передаваемой кодовой комбинации, обозначим набор этих символов как подмножество {a_j}.Таким образом, для нахождения r проверочных разрядов необходимо последовательное применение r различных операторов R_i (проверок):