Циклические коды составляют большую группу наиболее широко используемых на
 Скачать 201 Kb.
|
|
2 G X( ), , второй вариант кода Хемминга.
1.5.3. ПРИНЦИПЫ ФОРМИРОВАНИЯ И ОБРАБОТКИ РАЗРЕШЕННЫХ КОДОВЫХ
КОМБИНАЦИЙ ЦИКЛИЧЕСКИХ КОДОВ
На основании материалов предыдущего раздела можно дать следующее
определение циклических кодов (ЦК). Циклические коды составляют множество
многочленов Вi(Х) степени n-1 и менее (до m n k = − , где m – число проверочных
символов), кратных порождающему (образующему) полиному G(Х) степени m, который, в
свою очередь, должен быть делителем бинома 1
n
X + , т. е. остаток после деления бинома
на G(X) должен равняться нулю. Учитывая, что ЦК принадлежат к классу линейных,
групповых кодов, сформулируем ряд основных свойств, им присущих.
1) Сумма разрешенных кодовых комбинаций ЦК образует разрешенную кодовую
комбинацию
( ) ( ) ( ). B X B X B X i j k ⊕ = (1.26)
2) Поскольку к числу разрешенных кодовых комбинаций ЦК относится нулевая
комбинация 000 ... 00, то минимальное кодовое расстояние dmin для ЦК
определяется минимальным весом разрешенной кодовой комбинации:
min min
d W= . (1.27)
3) Циклический код не обнаруживает только такие искаженные помехами кодовые
комбинации, которые приводят к появлению на стороне приема других
разрешенных комбинаций этого кода из набора Nn.
4) Значения проверочных элементов m = n – k для ЦК могут определяться путем
суммирования «по модулю 2» ряда определенных информационных символов
кодовой комбинации Аi(Х). Например, для кода Хемминга (7,4) с порождающим
полиномом G(X) = X
3
+ Х + 1 алгоритм получения проверочных символов будет
следующим:
1 1 2 3
r i i i = ⊕ ⊕ ,
2 2 3 4
r i i i = ⊕ ⊕ ,
3 1 2 4
r i i i = ⊕ ⊕ .
(1.28)
Эта процедура свидетельствует о возможности «поэлементного» получения
проверочной группы для каждой кодовой комбинации Аi(Х). В соответствии с (1.28) могут
строиться кодирующие устройства для ЦК.
5) Умножение полинома на X приводит к сдвигу членов полинома на один разряд
влево, а при умножении на X
m
, соответственно, на r разрядов влево, с заменой m
младших разрядов полинома «нулями». Умножение полинома на X свидетельствует
о том, что при этой процедуре X является «оператором сдвига». Деление полинома
на X приводит к соответствующему сдвигу членов полинома вправо с уменьшением
показателей членов на 1. Процедура сдвига позволяет к исходной кодовой
комбинации Аi(Х) после умножения ее на X
m
, дописать справа m проверочных
символов. 30 .
3600
1.1 10
1.1 10
10
1.1 10
10
2
5
5
7
12
7
40
час
c
c
V
N
T
ЭВМ
n
ДК =
⋅
= ⋅ =
⋅
= = =
6) Поскольку разрешенные кодовые слова ЦК Bi(X) без остатка делятся на
порождающий полином G(X) с получением итога в виде информационной
комбинации Аi(Х) (1.17), то имеется возможность формировать Bi(X) на стороне
передачи (кодирующее устройство) простым методом умножения (1.18).
Два последних свойства ЦК позволяют осуществить построение кодеров ЦК двумя
методами: методом умножения и методом деления полиномов. Рассмотрим достоинства и
недостатки этих методов с учетом вариантов построения декодеров ЦК, соответствующих
этим методам.
Метод умножения позволяет при формировании разрешенных кодовых комбинаций
по алгоритму (1.18) использовать любой порождающий полином, лишь бы его
максимальная степень была равна числу необходимых проверочных символов m.
Однако этот метод обладает двумя существенными недостатками.
Во-первых, при формировании ЦК методом умножения в полученной комбинации
Bi(X) в явном виде не содержатся информационные символы. Код получается
неразделимым с «перетасованными» информативными и проверочными символами, что
затрудняет его декодирование, так как это приводит к необходимости применять метод
максимального правдоподобия в декодирующем устройстве (ДУ).
Метод максимального правдоподобия (ММП) предполагает при исправлении
ошибок принимаемую кодовую комбинацию отождествлять с той разрешенной, к которой
принятая находится ближе всего. При таком непосредственном способе декодирования в
памяти запоминающего устройства (ЗУ) декодера необходимо хранить все разрешенные
кодовые комбинации Nn, что требует на стороне приема больших объемов ЗУ и большого
времени обработки при декодировании. Эти обстоятельства являются вторым недостатком
метода умножения при кодировании ЦК.
Исследования показывают, что хороший циклический корректирующий код с
кратностью исправляемых ошибок gи ≥ 5 при относительной скорости кода Вк ≥ 0.5, т. е.
коэффициенте избыточности x ≤ 0.5, должен иметь число информационных символов k ≥
40. Это значение и приводит к техническим трудностям при процедуре декодирования по
ММП, сводящейся к сравнению принятой кодовой комбинации со всеми Nn разрешенными.
Для примера определим время декодирования TДК
принятой кодовой комбинации,
если число информационных символов в ней k = 40 и для сравнения используется ЭВМ со
скоростью 10
7
операций в секунду.
Будем полагать, что для сравнения принятой кодовой комбинации с одной из
разрешенных достаточно одной операции на ЭВМ. Тогда для проведения
40
2 2
n k
N = =
сравнений потребуется время декодирования Как видно из примера, задача декодирования простым перебором и сравнением
непосильна даже для современных ЭВМ.
В соответствии с этим, основным направлением в теории кодирования является
поиск таких кодов и алгоритмов их формирования и обработки, для которых не требуется
хранение в ЗУ разрешенных кодовых комбинаций. Эти задачи решаются, в частности, при
построении кодеров на основе деления полиномов, а при декодировании – на основе
синдромного метода декодирования (СМД).
Метод деления полиномов позволяет представить разрешенные к передаче
кодовые комбинации в виде разделенных информационных Ai(X) и проверочных Mi(X)
символов, т. е. получить блочный код.
Поскольку число проверочных символов равно m, то для компактной их записи в
последние младшие разряды кодового слова надо предварительно к Ai(X) справа приписать
m «нулей», что эквивалентно умножению Ai(X) на оператор сдвига X
m
(см. свойство 5 ЦК).
На практике предпочитают использование метода деления полиномов при
построении кодеков, поскольку при этом имеется возможность представить кодовую
комбинацию в виде разделенных информационных и проверочных символов:
( ) ( ) ( ),
m
B X A X X R X i i i = +
(1.29)
где ( ) R Xi
– остаток от деления ( ) / ( ).
m
A X X G X i
В алгоритме (1.29) можно выделить три этапа формирования разрешенных кодовых
комбинаций в кодирующем устройстве:
1) к комбинации первичного кода Ai(X) дописывается справа m нулей, что
эквивалентно умножению Ai(X) на X
m
;
2) произведение Ai(X) X
m
делится на соответствующий порождающий полином G(X) и
определяется остаток Mi(X), степень которого не превышает m – 1, этот остаток и
дает группу проверочных символов;
3) вычисленный остаток присоединяется справа к Ai(X) X
m
.
Синдромный метод декодирования (СМД) предполагает в ДУ принятую кодовую
комбинацию поделить на порождающий полином. Если принятая комбинация является
разрешенной, т. е. не искажена помехами в канале связи, то остаток от деления будет
нулевым. Ненулевой остаток свидетельствует о наличии в принятой кодовой комбинации
ошибок, остаток от деления и называется синдромом.
Термин «синдром» заимствован из медицинской практики (от греч. вместе бегущий)
и означает сочетание (комплекс) симптомов болезни, характерное для определенного заболевания. В теории кодирования синдром, который также называют опознавателем
ошибки, обозначает совокупность признаков, характерных для определенной ошибки. Для
исправления ошибки на стороне приема необходимо знать не только факт ее
существования, но и ее местонахождение, которое определяется по установленному виду
вектора ошибки z (X).
После передачи по каналу с помехами принимается кодовое слово
'
( ) ( ) ( ), B X B X z X i i = + (1.30)
где Bi(X) – передаваемая кодовая комбинация; z(X) – полином (вектор) ошибки, имеющий
степень от 1 до n – 1.
При декодировании принятое кодовое слово делится на G(X )
'
( )
( ) ( ),
( )
i
i i
B X
U X S X
G X
= + (1.31)
где остаток от деления Si(X) и является синдромом.
Если при делении получается нулевой остаток Si(X) = 0, то выносится решение об
отсутствии ошибки z(X) = 0. Если остаток (синдром) ненулевой Si(X) ≠0, то выносится
решение о наличии ошибки и определяется шумовой вектор (полином) z(X), а затем –
передаваемое кодовое слово, поскольку из (1.30) следует
'
( ) ( ) ( ). B X B X z X i i = +
Всякому ненулевому синдрому соответствует определенное расположение
(конфигурация) ошибок. Взаимосвязь между видом синдрома и местоположением
ошибочного символа находится довольно просто. Достаточно в любую разрешенную
кодовую комбинацию ввести ошибку и выполнить деление на G(X). Полученный остаток
(1.31) – синдром и будет указывать на ошибку в этом символе.
1.5.4. ПОСТРОЕНИЕ ПОРОЖДАЮЩИХ И ПРОВЕРОЧНЫХ МАТРИЦ ЦИКЛИЧЕСКИХ
КОДОВ
Наряду с полиномиальным способом задания кода, структуру построения кода
можно определить с помощью матричного представления. При этом в ряде случаев проще
реализуется построение кодирующих и декодирующих устройств ЦК.
Рассмотрим варианты формирования и обработки ЦК, заданных в виде
порождающих и проверочных матриц, на конкретном примере ЦК Хемминга (7,4),
воспользовавшись выражением (1.25), в котором определены двойственные (дуальные)
порождающие полиномы кода: 7 3 2 3
1 2 3 X X X X X X G X G X G X + = + + + + + = × × 1 ( 1)( 1)( 1) ( ) ( ) ( ) ,
что соответствует кодам (7, 6), (7, 4) и (7, 4).
Пример
Задан ЦК(7,4) дуальными порождающими полиномами
3
G X X (7,4) 1 = + + и