71
Кодер систематического кода заполняет первые k позиций информационными символами, поступившими на его вход. На оставшиеся r позиций он ставит проверочные символы, при этом вычисляет их значения так, чтобы для n-разрядной выходной комбинации оказалось c=0. Для рассмотренного примера s2 a2 , а из соотношений (3.11) находим три проверочных
символа, завершая кодирование:
s3 s1, s4 s1 s2 , s5 s2 . |
(3.15) |
Первый этап декодирования принятой n-разрядной комбинации y – это |
|
обнаружение ошибок, и он также определяется соотношением (3.14) |
|
c yHT . |
(3.16) |
Напомним, что в соответствии с (3.2) вектор ошибок e позволяет выразить принятую комбинацию y через переданную s, то есть y=s+e. Подставим эту сумму в (3.16) и напомним, что для любой передаваемой комбинации sHT 0 . В итоге получим
c (s e)HT sHT eHT eHT , |
(3.17) |
то есть, синдром, вычисленный по принятой комбинации, не зависит от того, какая комбинация из кодовой таблицы была передана, а определяется лишь вектором ошибок. Именно по этой причине при обсуждении операций декодирования у нас не возникло потребности обращаться к кодовой таблице, а ограничились лишь анализом предполагаемого характера возникающих ошибок. Нетрудно догадаться, что и табл. 3.3. была составлена с использованием формулы (3.17), то есть
Не нужно строить код так, чтобы результат какой-либо проверки на чётность следовал из остальных проверок – это пустая трата ресурсов. Кроме того, любой из n символов комбинации должен участвовать хотя бы в одной проверке. При выполнении этих условий любой матрице H соответствует единственная матрица G размера (k n) , называемая производящей (генера-
торной) матрицей данного кода. Обе матрицы связаны уравнением |
|
GHT 0, |
(3.18) |
где 0 – нулевая матрица размера (k r).
Если задана матрица H, то, решив уравнение (3.18), можно найти матрицу G. Процедура решения оказывается простой, если код является систе-
матическим. Тогда |
и матрицу G условно можно разбить на два блока |
|||
G (Ik ,QT ) , где Ik – |
единичная матрица (k k) . Используя блочные представ- |
|||
ления обеих матриц, имеем |
|
|
|
|
|
QT |
|
|
|
|
GHT (Ik , QT ) |
|
QT QT 0, |
(3.19) |
|
Ir |
|
|
|
|
|
|
||
то есть построенная таким образом матрица G удовлетворяет уравнению (3.18). В частности, для (5,2)-кода (3.11) матрица G имеет вид
72
10110 |
|
|
|
G |
|
. |
(3.20) |
|
01011 |
||
Из сказанного ясно, что матрица G, как и матрица H, полностью определяет код. Поэтому другая интерпретация тех же процессов кодирования и декодирования может быть основана на матрице G.
Кодирование линейным блочным кодом можно проводить по формуле
(3.21)
Используя определение (3.18), видим, что синдром для полученной таким образом кодовой комбинации всегда равен нулю
c sHT aGHT a0 0, |
(3.22) |
то есть эта комбинация входит в кодовую таблицу.
Возможность декодирования (вычисления синдрома) принятой комбинации с использованием матрицы G становится вполне очевидной, если код является систематическим (3.10). Из принятой комбинации sп (aп ,bп ) берут
вектор-строку информационных символов ап и по ней заново проводят кодирование, например, по формуле (3.21), получая новое значение векторастроки проверочных символов bн
s |
н |
a |
G a |
(I |
k |
,QT ) (a |
,a |
QT ) (a |
,b |
н |
). |
|
(3.23) |
|||
|
п |
п |
|
|
|
п |
п |
|
п |
|
|
|
|
|||
По определению (3.16), вектор-синдром для принятой комбинации sп |
||||||||||||||||
равен |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
QT |
aпQT bп |
bн bп |
|
|
||||||
c sпHT (aп ,bп ) |
|
, |
(3.24) |
|||||||||||||
|
|
|
|
|
|
Ir |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
то есть для вычисления синдрома достаточно сложить два вектора проверочных символов: принятый и вновь вычисленный.
Кроме способности обнаруживать и исправлять ошибки, блочные коды обладают еще и способностью восстанавливать стертые символы (см. разд.
2.11).
Допустим, проведено кодирование рассмотренным кодом (5,2), и комбинация на входе декодера имеет вид 1X10X, где буквой X обозначены позиции стертых символов. Считаем, что остальные символы ошибок не содержат. В первой проверке на четность (рис. 3.1) стертые символы не участвуют. Чтобы удовлетворить требованиям второй проверки, на вторую позицию в этой комбинации нужно поставить 1, тогда она примет вид 1110X. Из третьей проверки видно, что и последний символ должен быть единицей. В итоге принято решение, что была передана четвертая комбинация из кодовой таблицы.
Можно на примерах убедиться в том, что код гарантированно может восстановить любые qc стертых символов, если qc удовлетворяет тому же условию (3.5).
В заключение сделаем несколько замечаний.
1) Любой линейный блочный код обладает следующим свойством: если
73
из кодовой таблицы взять две (или более) комбинаций и сложить их (разумеется, по модулю 2), то получим комбинацию, принадлежащую той же таблице.
2)Операцию умножения вектора-строки на матрицу удобно провести следующим образом: элементы этого вектора записываем против строк матрицы, а затем суммируем те строки, против которых оказались единицы.
3)По определению (3.4) кодовое расстояние нужно находить по кодовой таблице. Для линейных блочных кодов существует менее трудоёмкий способ: к матрице G нужно дописать строку, состоящую из нулей, и тем же способом (3.4) определить минимальное расстояние для полученной таблицы.
4)Каждая строка проверочной матрицы H соответствует одной проверке на четность, причем положение единиц в этой строке указывает на позиции символов кодовой комбинации, участвующих в данной проверке.
5)Каждый столбец проверочной матрицы H соответствует синдрому для однократного ошибочного символа, номер которого в кодовой комбинации совпадает с номером столбца. Это позволяет по матрице H определить
корректирующую способность кода. Так. Код способен обнаружить только однократную ошибку, если все столбцы ненулевые и есть одинаковые. Будет обнаружена двукратная ошибка или исправлена однократная, если все столбцы ненулевые и разные. В общем случае кодовое расстояние равно минимальному числу линейно зависимых столбцов матрицы H.
6)Одновременная одинаковая перестановка столбцов матриц G и H даёт новый код, эквивалентный исходному, поскольку это приводит к аналогичной перестановке соответствующих символов во всех кодовых комбинациях. Тот же результат будет, если один из двух столбцов заменить их суммой. Многократное повторение подобных операций можно применить, например, для приведения кода к систематической форме.
7)Применяются два способа реализации кодера и декодера: программный (при использовании компьютера) и аппаратный. При аппаратной реализации кодирования для любого линейного блочного кода можно применить такой универсальный (следовательно, не самый экономный) способ: входную k - разрядную последовательность информационных символов последовательно, символ за символом, ввести в k – разрядный входной регистр сдвига, чтобы иметь возможность проводить одновременно операции со всеми символами; при помощи набора сумматоров по модулю 2 вычислить раздельно все n символов кодовой комбинации по формуле (3.21) с учётом примечания 2 (для систематического кода можно ограничиться вычислением лишь проверочных символов по формулам типа (3.15)); при помощи n-входового мультиплексора вывести последовательно все n символов в нужном порядке (разумеется, и для вывода символов можно применить n-разрядный регистр сдвига, предварительно записав в него n вычисленных символов кодовой
74
комбинации).
Универсальный способ декодирования предполагает следующие действия: n принимаемых символов последовательно вводятся в n-разрядный регистр сдвига; при помощи набора сумматоров по модулю 2 вычисляют все r элементов синдрома по формулам типа (3.11) (можно подсчитать потребное количество сумматоров даже с учётом дублирования некоторых операций); при помощи логического устройства (назовём его анализатором синдрома), пользуясь таблицей (e–c), по вычисленному значению c находят e, то есть номера ошибочных символов; при помощи k-входового мультиплексора принятые информационные символы последовательно подают на вход сумматора по модулю 2, а на второй вход сумматора в том же порядке с анализатора синдрома подают найденные элементы вектора ошибок, в итоге в этом сумматоре ошибки последовательно исправляются в процессе вывода информационных символов.
8) Избыточность (в техническом смысле) для линейного блочного кода
равна
R r / n. |
(3.25) |
Увеличить кодовое расстояние (и корректирующую способность) кода при заданном n удаётся лишь ценой увеличения избыточности, поэтому ос-
новной девиз помехоустойчивого кодирования – минимальное значение r при заданных n и dкод .
9) Код, укороченный по сравнению с исходным систематическим кодом, получают следующим образом: для передачи сообщения используют лишь последние m позиций k-разрядного вектора a, а первые k-m позиций заполняют нулями, затем кодируют обычным образом. По линии связи передаётся укороченная комбинация, а в пункте приёма перед декодированием записывают нули на недостающие позиции. При таком укорочении и r не
изменяются, но избыточность возрастает за счёт уменьшения n, поэтому этот способ следует применять лишь в случае крайней необходимости.
3.3 Коды Хэмминга
Продолжим рассмотрение линейных блочных кодов, обладающих кодовым расстоянием dкод 3 и в соответствии с (3.6) способных исправить лю-
бую одиночную ошибку в принятой n-разрядной комбинации.
Таблица (e–c) типа табл. 3.3 содержит n строк, при этом все значения r- разрядного вектора c должны быть различными. Тогда максимально-
возможное значение n определяется формулой |
|
|
n n |
2r 1, |
(3.26) |
max |
|
|
где вычитание единицы обусловлено тем, что нулевая комбинация, соответствующая отсутствию ошибок, в таблице не содержится.
75
Коды, обладающие такими параметрами, называются кодами Xэм-
минга. К ним относятся коды (3,1), (7,4), (15,11), (31,26) и т.д.
Кстати, код (5,2), рассмотренный в разделе 3.2, также имеет dкод 3 , но
не является кодом Хэмминга.
Напомним, что эта таблица (e-c) построена с использованием формулы c eHT , и в ней значения вектора-синдрома совпадает с соответствующими столбцами матрицы H, поэтому даже нет нужды в построении этой таблицы. К сожалению, такое простое соответствие характерно только для кодов, исправляющих одиночные ошибки.
Итак, для кода Хэмминга в качестве столбцов матрицы H нужно записать различные r-разрядные двоичные числа, кроме нулевого (красота идеи построения кода Хэмминга станет позже более понятной, если их записать в порядке возрастания).
Для примера запишем матрицу H для (7,4)-кода
0001111 |
|
||
|
|
(3.27) |
|
H 0110011 . |
|||
|
|||
1010101 |
|
||
|
|
|
|
В качестве проверочных для кода Хэмминга можно считать любые r символов, но вычисление их значений при кодировании слегка упрощается, если в качестве проверочных взять те символы, которые охвачены лишь одной проверкой на чётность. В нашем примере это s1, s2, s4, тогда информационными символами будут s3, s5, s6, s7. Перестановкой символов код можно привести к систематическому виду, но пользы от такой операции в данном случае пока не видно.
Кодирование для (7,4)-кода проводится следующим образом: четыре информационных символа a1, a2 , a3, a4 , поступившие на вход кодера, записы-
ваются на позиции s3, s5, s6, s7, а затем находят три проверочных символа по той же методике, как и (3.15)
s1 s3 s5 s7 , |
s2 s3 s6 s7 , |
s4 s5 s6 s7 . |
(3.28) |
Декодирование начинается с вычисления синдрома (3.16). Если c=0, считают, что ошибок нет. В противном случае вычисленное значение c совпадает с номером ошибочного символа, записанным в двоичной форме.
Для (7,4)-кода вычисление элементов синдрома проводится по форму-
лам
c1 s4 s5 s6 s7 , |
c2 s2 s3 s6 s7 , c3 s1 s3 s5 s7 . |
(3.29) |
Например, для принятой комбинации y=0111100 имеем c=000, поэтому |
||
считываем значения y3 , y5 , y6 , y7 |
и подаём их на выход декодера (проверочные |
|
символы свою роль уже сыграли и получателю они не нужны). Для комбинации 1010001 имеем c=101, то есть ошибка в пятом символе – его нужно изменить на обратный (0 на 1).
Код Хэмминга определён формулой (3.26), поэтому он является опти-