Файл: прикладная теория информации.pdf

176
Пример 10.4. Произвести синтез функциональной схемы вычисления синдрома, используя форму (9.15) матрицы ????для входного процесса
???? = ???? + ???? = (????
0
????
1
????
2
????
3
????
4
????
5
????
6
).
Решение. По формуле (10.2) вычисляем синдром
???? = ????????
????
= [
1 0 1 0 1 0 1
0 1 1 0 0 1 1
0 0 0 1 1 1 1
] [(????
0
????
1
????
2
????
3
????
4
????
5
????
6
)]
????
= (????
0
????
1
????
2
)
????
Элементы вектора синдрома равны:
????
0
= ????
0
+ ????
2
+ ????
4
+ ????
6
,
????
1
= ????
1
+ ????
2
+ ????
5
+ ????
6
,
????
2
= ????
3
+ ????
4
+ ????
5
+ ????
6
На рис. 10.1 показана функциональная схема вычисления синдрома
Рис. 10.1. Вычислитель синдрома
10.2.1. Эффективность синдромного декодирования
Тот факт, что все элементы одного и того же смежного класса имеют один и тот же синдром, позволяет упростить процедуру декодирования в сравнении с декодированием по таблице стандартного расположения для кода. Сравним тех- ническую сложность декодирования по таблице смежных классов и синдромного декодирования с использованием таблицы синдромов.
Процесс декодирования по таблице стандартного расположения для кода требует проведения операций сравнения входного слова со всеми элементами таблицыразмером 2
????
× 2
????
. Для декодирования слов значностью n необходима память объемом

177
???? = ????2
????+????
= ????2
????
бит.
Таблица стандартного расположения содержит 2
????
строк (смежных клас- сов) и 2
????
разных синдромов. Для хранения всех векторов столбца лидеров смеж- ных классов потребуется объем памяти величиной
????
????
= ????2
????
бит.
Выигрыш по объему памяти декодера составит значение
???? =
????
????
????
=
????2
????
????2
????
= 2
????
бит.
10.3. Декодирование кода Хэмминга
Согласно теореме 10.1, синдром принятого вектора равен сумме тех столб- цов матрицы ????, где произошли ошибки. Для того, чтобы построить код, исправ- ляющий одну ошибку, необходимо выбрать столбцы матрицы ???? следующим об- разом:
– столбцы должны быть ненулевыми (иначе ошибка в этой позиции будет необнаруженной);
– столбцы должны быть различными (иначе, если два столбца матрицы ???? одинаковы, то ошибки в соответствующих двух позициях будут неразличимы).
Если матрица ???? имеет ???? строк, то существует только 2
????
− 1 допустимых ненулевых двоичных векторов длиной ????. Проверочная матрица кода Хэмминга содержит столбцы, которые являются двоичными представлениями чисел от 1 до
????.
Используя такую матрицу (9.15), в которой i-й столбец ????
????
равен двоичному представлению числа ????, по синдрому легко определяется номер ошибочного сим- вола принятого слова.
Замечание. Более простой технической реализацией алгоритма синдром- ного декодирования, чем по матрице классического вида кода Хэмминга, не су- ществует.
10.4. Вычисление вероятности ошибки декодирования
10.4.1. Распределение весов ошибок

178
На длине ???? кодового слова возможны следующие ошибки:
– одиночные, ???? = 1;
– двойные, ???? = 2;
– трехкратные, ???? = 3 и т. д.
На длине кодового слова возможны различные конфигурации ошибок – векторы ошибок различного веса и формы. Обозначим ????
????
как число всех конфи- гураций ошибок веса ????. Это число определяется биноминальным коэффициентом
????
????
????
=
????
????
????
????
????
=
????(????−1)…(????−????+1)
????!
Пример 10 .5 . Найти распределение весов ошибок на длине ???? = 5 кодо- вого слова. Число конфигураций ошибок равно:
????
1
= ????
5 1
= 5,
????
2
= ????
5 2
=
????
5 2
????
2
=
????(????−1)
2!
=
5∙4 2
= 10,
????
3
= ????
5 3
=
????
5 3
????
3
=
????(????−1)(????−2)
3!
=
5∙4∙3 2∙3∙
= 10,
????
4
= 5, ????
5
= 1.
Суммарное число возможных конфигураций ошибок на длине ???? составит величину
????
∑
= ∑ ????
????
????
????
????
= ∑ ????
????
????
????=1
= 2
????
− 1.
Для приведенного примера
????
∑
= ????
1
+ ????
2
+ ????
3
+ ????
4
+ ????
5
= 31.

179
Prob{
????
wt(1
????
)
} = ????
????
1
????
1
(1 − ????)
????−????
Пример 10.6. Пусть ???? = 0,2, ???? = 5. Вычислить вероятности возникно- вения хотя бы одной конфигурации однократной и двукратной ошибки.
Решение. Вероятность возникновения хотя бы одной конфигурации одно- кратной ошибки равна
Prob{
????
wt(1
????
)
} = ????
????
1
????
1
(1 − ????)
????−1
≅ 5 ⋅ 0,081 ≅ 0,4.
Вероятность того, что имеется хотя бы одна конфигурация двукратной ошибки равна
Prob{
????
wt(2
????
)
} = ????
????
2
????
2
(1 − ????)
????−2
≅ 10 ⋅ 0,01 ≅ 0,1.
Вновь подтверждается, что ошибки малого веса необходимо обнаруживать и исправлять в первую очередь.
В общем случае, вероятность того, что в слове длиной ???? содержится хотя бы одна ошибка кратностью ???? или величины веса ???? равна
Prob{
????
????????(????
????
)
} = ????
????
????
????
????
(1 − ????)
????−????
. (10.3)
Определение 10.3. Вероятностью ошибки декодирования кодового слова называется вероятность появления неправильного кодового слова на выходе де- кодера.
Пусть имеется код мощностью ????. Слова кода ????
1
, ????
2
, … , ????
????
, … , ????
????
переда- ются по каналу с равной вероятностью. Тогда средняя вероятность ошибки де- кодирования на кодовое слово определяется выражением
????
????
=
1
????
∑ Prob{слово на выходе декодера ≠ ????
????
|????
????
было передано}
????
????=1
Декодирование осуществляется с использованием таблицы стандартного расположения для кода. Напомним, что выбранный декодером вектор ошибки всегда есть один из лидеров смежных классов. Ошибка декодирования происхо- дит тогда и только тогда, когда вектор ошибок не является лидером смежного класса, т. е.
????
????
= Prob{???? ≠ лидер смежного класса}.
Предположим, что в таблице стандартного расположения имеется ????
????
лидеров смежных классов веса ????, т. е. число векторов ошибок веса ???? равно ????
????
Используя (10.3), найдем вероятность того, что вектор ???? ошибки является лиде- ром смежного класса

180
Prob{???? = лидер смежного класса} = ∑
????
????
????
????
(1 − ????)
????−????
????
????=0
. (10.4)
Выражение (10.4) характеризует правильное декодирование. Вероятность не появления события (10.4) представляется как вероятность ошибки декодиро- вания (вероятность появления неправильного кодового слова на выходе деко- дера):
????
????
= 1 − ∑
????
????
????
????
(1 − ????)
????−????
????
????=0
. (10.5)
Если код имеет кодовое расстояние ???? = 2???? + 1, он исправляет все
????- кратные конфигурации ошибок. В этом случае диапазон весов ???? исправляемых векторов ошибок лежит в пределах 0 ≤ ???? ≤ ????.
Тогда, каждый вектор ошибок веса не более ???? является лидером смежного класса. Число лидеров смежного класса веса ???? для кода с минимальным расстоя- нием ???? = 2???? + 1 находится из выражения, полученного ранее для возможного числа ошибок кратностью ???? на длине ???? кодового слова, т. е.
????
????
= ????
????
????
Большинство известных кодов могут исправлять некоторые конфигурации ошибок для значений ???? > ????. Вычисление числа лидеров смежных классов для зна- чений ???? > ???? не простая задача. Эти числа известны только для немногих кодов.
Но если вероятность ошибки ???? в канале такова, что
(
1 − ????) ≅ 1,
????
????
(1 − ????)
????−????
≫ ????
????+1
(1 − ????)
????−????−1
, то в этом случае в формуле (10.5) пренебрегают членами с большими значениями
????. Тогда вероятность ????
????
ошибки декодирования кодового слова на основе таб- лицы стандартного расположения определяется по формуле
????
????
≅ 1 − ∑
????
????
????
????
????
(1 − ????)
????−????
????
????=0
. (10.6)
Пример 10 .7 . Определить ошибку декодирования кодового слова кода
[4, 2, 2], используя стандартное расположение для кода (табл. 10.2), вероятность ошибки на символ p = 0,2.
Решение. По таблице находим число лидеров смежных классов веса ????:
????
????=0
= 1, ????
????=1
= 3.
По формуле (10.5) получаем

181
????
????
= 1 − ∑ ????
????
????
????
(1 − ????)
????−????
????
????=0
= 1 − ∑ ????
????
????
????
(1 − ????)
4−????
4
????=0
=
= 1 − ????
0
(1 − ????)
4
− 3????
1
(1 − ????)
3
= 1 − 0,8 4
− 3 ∙ 0,2 ∙ 0,8 3
= 0,2832.
10.5. Задание для самостоятельного выполнения
1. Построить порождающую
???? и проверочную ???? матрицы линейного груп- пового кода с параметрами [5, 2, 3].
2. Используя порождающую матрицу
???? кода (п. 1), записать все слова кода.
3. Используйте синдромный метод для декодирования кода
???? (п. 1), если на выходе канала формирются векторы
????
1
= (11001), ????
2
= (11101).
4. Используйте метод синдромного декодирования линейного группового кода (см. подразд. 9.9, п. 4, п. 5) для контроля над ошибками, если получены слова:
????
1
= (110101), ????
2
= (111001).
5. Используйте метод декодирование кода (см. подразд. 9.9, п. 4, п. 5) на основе принципа максимального правдоподобия, если получены слова
????
1
= (11001), ????
2
= (11101).
6. Произвести синтез функциональной схемы вычисления синдрома, ис- пользуя форму матрицы ????(п. 1) для входного процесса ???? = ???? + ???? =
(????
0
????
1
????
2
????
3
????
4
????
5
).
7. Определить ошибку декодирования кода [6, 3, 3] в канале с вероятно- стью ошибки на символ ???? = 0,01, используя стандартное расположение для кода, представленного матрицей
???? = [
1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0
].

182
11. КОНСТРУКЦИИ ЦИКЛИЧЕСКИХ КОДОВ
Важным подклассом линейных блочных кодов являются двоичные цикли- ческие коды (ЦК). Код легко реализуется на регистре сдвига (РС) с обратной свя- зью. Схема, построенная на регистрах сдвига с обратной связью, позволяет срав- нительно просто вычислять синдром, и таким образом, эффективно реализовать процесс декодирования ЦК. Алгебраические особенности ЦК позволяют эффек- тивно реализовать не только синдромное декодирование, но и спектральные и другие более затратные методы оптимального декодирования. Эти и другие осо- бенности, связанные с широким применением ЦК в современных инфокоммуни- кациях, определяются их алгебраическими свойствами.
Другие характеристики циклических кодов:
– содержат семейства БЧХ- кодов и РС- кодов;
– являются основой для построения конструкций комбинированных кодов;
– используются для построения конструкций низкоскоростных кодов.
Теория линейных циклических кодов основывается на многочленном (по- линомиальном) представлении, когда построение кода осуществляется с помо- щью операций сложения, вычитания и умножения полиномов по модулю поли- нома
1.
n
x

Множество слов циклического кода
{ ( )}
с
c x
G


попадает в класс вычетов многочленов в степени не больше (???? ‒1).
11.1. Алгебраическое описание циклических кодов
Определение 11.1. Линейный
)
,
,
(
d
k
n
-код называется циклическим, если он линеен и обладает свойством цикличности, если кодовое слово (вектор)
0 1 1
(
)
n
с с с


с
принадлежит коду
{ }

G
c
, то вектор "
1 0 1 2
(
)
n
n
с c с с




с
G
также является кодовым вектором циклического кода.
Например, код
0 0
0 0
1 1
1 0
1 1
1 0













G
(11.1) является циклическим.
Введём следующие обозначения:
p
– простое число;
F
– конечное поле Галуа,
( )
F
GF p

;
n
F
–
n
-мерное пространство над полем
( )
GF p
R
– кольцо.
{ ( )}
R
F x

– множество многочленов от
x
с коэффициентами из
F
;
(
1)
n
x

– многочлен степени
n
над полем
( )
GF p
;

183
{ ( )}
(
1)
(
1)
n
n
n
R
F x
R
x
x




– классы вычетов кольца
R
по модулю многочлена
(
1)
n
x

n
R
–
n
-мерное пространство над полем
( )
GF p
При описание многих конструкций ЦК используют как векторное, так и многочленное представление кодов. Сопоставим каждому вектору
0 1 1
(
)
n
с с с


с
из
n
-мерного пространства над полем
( )
GF p
многочлен
)
(
1 1
1 0






n
n
x
c
x
c
c
x
c
Например, векторам кода
G
(11.1) соответствуют многочлены:
2 2
0
( )
1 1
x
x
c x
x
x
















(11.2)
Умножение многочлена
1 0
1 1
( )
(
)
n
n
с x
с
с x
с
x




 
на
( )
x
в кольце
n
R
.
В результате умножения получаем
1 2
1 0
1 1
0 1
2 1
( )
(
)
(
),
n
n
n
n
n
n
с x x
с
с x
с
x
x
с x с x
с
x
с
x







 


 

2 1
1 0
1 2
( )
(
).
n
n
n
c x x
с
с x с x
с
x






 
(11.3)
Многочлену (11.3) соответствует вектор
1 0 1 2
(
).
n
n
с с с с


Следовательно, в кольце
n
R умножение на
( )
x
соответствует цикличе- скому сдвигу вправо элементов вектора. В кольце
n
R имеет место равенство
),
1
mod(
0
)
1
(



n
n
x
x
отсюда
1
))
((

n
x
Пример 11 .1 . Заданы: модульный многочлен
4
( )
(
1)
z x
x


над полем
(2)
GF
и многочлен
3
( )
(
).
c x
x
x


Найти
( )
c x x
Решение.
3 2
4 2
4 2
( )
(
)
(1
) mod(1
)
((1
)).
c x x
x
x x
x
x
x
x
x




 



Определение 11.2. Циклический код длиной
n
есть идеал в кольце
n
R
мно- гочленов по модулю многочлена
( )
(
1)
n
z x
x


Напомним, идеалом
I
кольца
n
R
называется линейное подмножество
(подпространство) такое, что если многочлен
( )
c x
I

принадлежит идеалу, то

184 умножение этого многочлена на многочлен
( )
n
r x
R

дает новый многочлен, принадлежащий идеалу, т.е. справедливо выражение
( ) ( )
( )
, ( )
n
r x с x
l x
I r x
R



(11.4)
Выражение (11.4) может быть заменено на утверждение: если
,
)
(
I
x
c

то
)
(
I
x
xc

Пример 11.2 .Задан идеал
I
в виде подмножества многочленов (11.2).
Показать, что (11.2) образует циклический код.
Решение. Исходное подмножество является линейным, так как удовле- творяет свойству аддитивности и однородности. Например,
2 1
( )
(
)
c x
x
x
I



и
2
( )
(1
)
c x
x
I
  
, то
2 2
1 2
( )
( )
(
)
(1
)
(1
)
c x
c x
x
x
x
x
I



 
 

над полем
(2)
GF
Подмножество
I
замкнуто относительно операции сложения по модулю два. Пусть
2
( )
n
r x
x
R


. Вычислим произведение
2 2
3 4
3 1
( ) ( )
(
)
(
) mod(1
)
((1
))
r x с x
x x x
x
x
x
x
I








Как видно, любой многочлен
( )
r x
, кратный многочлену
I
x
c

)
(
принадле- жит идеалу. Множество слов циклического кода {????(????)} {попадает в класс выче- тов многочленов в степени не больше (???? ‒1), {????(????)} т.е. {????(????)} ∈ ???? = {????(????)}.
11.2. Порождающий многочлен циклического кода
Так как циклический код определяется понятием идеала кольца, то исходя из выражения (11.4)
( ) ( )
( )
r x с x
l x
I G

 
, можно утвеждать, что в идеале должен cуществовать некоторый фиксированный многочлен
( )
( )
с x
g x
I


, с помощью которого можно получить все множество
{ }

G
c
кодовых векторов ЦК. В этом случае код получается из произведений этого порождающего многочлена
( )
g x
на многочлены
( )
f x
кольца, выступающие в качестве информационных многочленов. Тогда правило кодирования любого информационного многочлена
( )
f x
должно удовлетворять выражению