Составители:
Рубрика:
11
5. Как было показано на примере в подразделе 1.2, умножение полинома на X при-
водит к сдвигу членов полинома на один разряд влево, а при умножении на X
r
, соответ-
ственно, на r разрядов влево, с заменой r младших разрядов полинома "нулями". Умно-
жение полинома на X свидетельствует о том, что при этой процедуре X является "опера-
тором сдвига". Деление полинома на X приводит к соответствующему сдвигу членов по-
линома вправо с уменьшением показателей членов на 1. Процедура сдвига позволяет к
исходной кодовой комбинации А
i
(Х), после домножения её на X
r
, дописать справа r про-
верочных символов.
6. Поскольку разрешённые кодовые слова ЦК B
i
(X) без остатка делятся
на порождающий полином G(X) с получением итога в виде информационной комбинации
А
i
(Х) (4.1), то имеется возможность формировать B
i
(X) на стороне передачи (кодирующее
устройство) простым методом умножения (4.2).
Два последних свойства ЦК позволяют осуществить построение кодеров ЦК двумя
методами: методом умножения и методом деления полиномов. Рассмотрим достоинства
и недостатки этих методов с учётом вариантов построения декодеров ЦК, соответствую-
щих этим методам.
Метод умножения позволяет при формировании разрешённых кодовых комбина-
ций по алгоритму (4.2) использовать любой порождающий полином, лишь бы его макси-
мальная степень была равна числу необходимых проверочных символов r.
Однако этот метод обладает двумя существенными недостатками.
Во-первых, при формировании ЦК методом умножения в полученной комбинации
B
i
(X) в явном виде не содержатся информационные символы. Код получается неразде-
лимым с "перетасованными" информативными и проверочными символами, что затруд-
няет его декодирование, так как это приводит к необходимости применять метод макси-
мального правдоподобия в декодирующем устройстве (ДУ).
Метод максимального правдоподобия (ММП) предполагает при исправлении
ошибок принимаемую кодовую комбинацию отождествлять с той разрешённой, к которой
принятая находится ближе всего. При таком непосредственном способе декодирования в
памяти запоминающего устройства (ЗУ) декодера необходимо хранить все разрешённые
кодовые комбинации N
0
, что требует на стороне приёма больших объёмов ЗУ и большого
времени обработки при декодировании. Эти обстоятельства являются вторым недостат-
ком метода умножения при кодировании ЦК.
Исследования показывают [5 - 8], что хороший циклический корректирующий код с
кратностью исправляемых ошибок g
u
≥ 5 при относительной скорости кода В
к
≥ 0,5, т. е.
коэффициенте избыточности к ≤ 0,5, должен иметь число информационных символов
k ≥ 40 . Это значение и приводит к техническим трудностям при процедуре декодирова-
ния по ММП, сводящейся к сравнению принятой кодовой комбинации со всеми N
0
раз-
решёнными.
Для примера определим время декодирования Т
дк
принятой кодовой комбина-
ции, если число информационных символов в ней k= 40 и для сравнения использует-
ся ЭВМ со скоростью 10
7
операций в секунду. Будем полагать, что для сравнения при-
нятой кодовой комбинации с одной из разрешённых достаточно одной операции на
ЭВМ. Тогда для проведения N
0
= 2
k
= 2
40
сравнений потребуется время декодирования
ч.
ЭВМ
к
Д
30
3600
5
1011
1011
10
1011
10
2
5
7
12
7
40
0
=
⋅
=⋅=
⋅
===
c
,
c,
,
V
N
T
Как видно из примера, задача декодирования простым перебором и сравнением
непосильна даже для современных ЭВМ.
В соответствии с этим, основным направлением в теории кодирования является
поиск таких кодов и алгоритмов их формирования и обработки, для которых не требуется
хранение в ЗУ разрешённых кодовых комбинаций. Эти задачи решаются, в частности,
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
