6. Простейшие помехоустойчивые коды

Код с постоянным весом. Одним из простейших блочных неразделимых кодов (см. рис.5.4) является код с постоянным весом. Примером такого кода может служить семибитный телеграфный код МТК-3, в котором каждая разрешенная кодовая комбинация содержит три единицы и четыре нуля (рис.5.7). Весом кодовой комбинации называют число содержащихся в ней единиц. В рассматриваемом коде вес кодовых комбинаций равен трем.

Число разрешенных кодовых комбинаций в кодах с постоянным весом определяется как количество сочетаний из n символов по g и равно

,

где n – длина кодовой комбинации, а g – вес разрешенной кодовой комбинации. Для кода МТК-3 число разрешенных кодовых комбинаций равно . Таким образом, из общего числа комбинаций N=2⁷=128 только 35 используются для передачи сообщений.

Избыточность кода с постоянным весом МТК-3

.

Минимальное кодовое расстояние такого кода d_min=2, что дает ему возможность обнаруживать однократные ошибки. Однако код с постоянным весом способен обнаруживать ошибки большей кратности (двойные, тройные и т.д.), при которых нарушается весовое соотношение единиц и нулей. Код не обнаруживает только ошибки, при которых число единиц, перешедших в нули, равно числу нулей, перешедших в единицы.

Следует отметить, что в настоящее время предпочтение отдается разделимым кодам, так как они проще реализуются.

Код с проверкой на четность. Этот код является наиболее простым блочным разделимым кодом, содержащим всего лишь один проверочный символ. Проверочный символ выбирается равным единице или нулю, таким образом, чтобы число единиц во вновь образованной n=k+1 – элементной кодовой комбинации было четным (рис.5.8).

Код с проверкой на четность относится к классу линейных систематических кодов. Формирование проверочных символов кодовых комбинаций кода с четным числом единиц осуществляется путем сложения по модулю 2 информационных символов. Например, к первичной комбинации 01011 следует добавить справа единицу, так как 01011=1, следовательно, разрешенная кодовая комбинация запишется так: 010111 (см. также рис.5.6).

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

Число разрешенных кодовых комбинаций равно:

,

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

Избыточность кода с проверкой на четность минимальна и равна

.

Для шестибитного кода (рис.5.8)

.

Минимальное кодовое расстояние кода с проверкой на четность равно двум (d_min=2). Легко убедиться, что проверка на четность позволяет выявить одиночную ошибку, поскольку она изменяет четность. Кроме однократных ошибок, этот код позволяет обнаруживать все ошибки нечетной кратности. Ошибки четной кратности код не обнаруживает. Например, если в кодовой комбинации будут искажены два символа, то четность не изменится и ошибка не будет обнаружена.

Код Бергера или код с контрольным суммированием является несистематическим кодом, у которого проверочные символы представляют собой двоичную запись числа единиц в последовательности информационных символов. Например, информационная последовательность 01011 содержит три единицы. Десятичному числу 3 соответствует двоичная запись 011, поэтому разрешенная кодовая комбинация кода Бергера примет вид: 01011011. Примеры разрешенных кодовых комбинаций данного кода приведены на рис.5.9, где проверочные символы обозначены затемнением.

Минимальное кодовое расстояние кода равно двум. Коды Бергера обнаруживают все одиночные ошибки и некоторую часть многократных ошибок. Эти коды обладают примерно такой же корректирующей способностью, что и код МТК-3, но имеют важное преимущество – они являются разделимыми, что упрощает реализацию кодирующих и декодирующих устройств.

Код с повторением является простейшим кодом, в котором информационные символы повторяются несколько раз. При этом может дублироваться -раз каждый символ или каждая информационная кодовая комбинация. Например, пятибитной информационной кодовой комбинации 11010 соответствует разрешенная комбинация кода с повторением при =2: 1111001100 или 1101011010. Таким образом, проверочными символами данного кода являются информационные символы. Код с повторением является разделимым систематическим кодом.

Основные характеристики кода зависят от числа повторений и равны:

, , .

Код с повторением способен не только обнаруживать ошибки, но и исправлять их. Однако для исправления даже одиночных ошибок требуется трехкратное повторение, т.е. трехкратное увеличение длины кода. Это слишком большая цена. Поэтому код с повторением хотя и применяется, но является низкоскоростным, поскольку имеет высокую избыточность. Например, при двукратном повторении минимальное кодовое расстояние равно двум (d_min=2), а избыточность K_и=0.5, которая существенно превышает избыточность, рассмотренных ранее кодов.

Код Бауэра (инверсный код). Этот код является разновидностью кода с двукратным повторением, обеспечивающим минимальное кодовое расстояние, равное четырем (d_min=4). При образовании данного кода, кодовые комбинации с четным числом единиц повторяются в неизменном виде (рис.5.10 а), а кодовые комбинации с нечетным числом единиц – в инвертированном (рис.5.10 б).

Код Бауэра называют также инверсным кодом. При небольших длинах кодовых комбинаций (n=10…14) инверсный код по своим корректирующим способностям не уступает более сложным кодам с такой же величиной избыточности.

Рекуррентный код (цепной код). Это непрерывный код, у которого проверочные символы чередуются с информационными по всей длине кодовой последовательности. Формирование проверочных символов в таких кодах осуществляется по рекуррентным правилам. В простейшем случае проверочные символы формируются путем суммирования по модулю 2 двух соседних информационных символов

, (5.7)

где b_i – i-й проверочный символ; a_i – i-й информационный символ, принимающий значение 0 или 1. Далее проверочные символы, сформированные по правилу (7), перемежаются с информационными, образуя непрерывную последовательность (рис.5.11).

Цепной код позволяет установить, какой из символов был искажен: информационный или проверочный. При приеме сравнивают принятые проверочные элементы с вычисленными, т.е. проверяют выполнение условия

. (5.8)

Искажение одного информационного символа a_i приводит к невыполнению (5.8) для двух символов: и. Таким образом, если условие (5.8) не выполняется для двух соседних проверочных элементов, то искаженным элементом является информационный элемент, находящийся между ними. Это означает, что его следует изменить на противоположный.

1На практике количество символов в блоке может лежать в пределах от трех до нескольких сотен.

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

3Напомним, чтократность ошибки– это число позиций кодовой комбинации, в которых под воздействием помех одни символы оказались замененными другими (нули – единицами, единицы - нулями).