Королёв А.И. Коды и устройства помехоустойчивого кодирования

Подождите немного. Документ загружается.

Отсюда следует, что для того чтобы найти (n,k)- код, исправляющий

.ош

t ,

достаточно построить (n,k)*n=l*n проверочную матрицу H(x), в которой любое

2*t столбцов линейно независимы. Для кода с (n,k,

) – параметрами можно

составить

−

− l

разных (по структуре столбцов) проверочных матриц

)x(H

n,l

;

4. Для СЛБК при декодировании и при отсутствии ошибок в кодовом слове

должно выполняться следующее равенство:

F′(x)·H

(x)=0 или F

(x)·H(x)=0.

При наличии ошибок эти равенства не выполняются и получаем

S(x)=F′(x)·H

(x),

где S(x)- двоичный вектор размерности (длины) l двоичных символов, который

носит название синдрома: (синдром- это совокупность признаков, а для ЛКБК

синдром – это совокупность нулевых и ненулевых символов).

Синдром для СЛБК является вектор длиной l=(n-k) двоичных символов,

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

(кодового слова) F′(x) на H

(x), т.е. S(x)=F′(x)·H

(x).

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

в виде соответствующих полиномов (F′(x)- степени (n-l), Q(x)- степени (k-l) и

P(x)- степени (n-k)=l) для синдрома имеется три тесно связанных друг с другом

записи, которые могут быть полезны в разных ситуациях [1,2]:

– первый вид синдрома или синдромный полином S(x) можно определить

как полином степени (n-k-l)=l-1, являющийся остатком от деления F′(x) /P(x),т.е.

S(x)= F′(x) /P(x).

Так как все кодовые последовательности (n,k)-кода должны делиться на P(x),

то S(x) не зависит от структуры переданной кодовой последовательности, а

зависит лишь от комбинации (структуры) ошибок;

– регистр сдвига с обратной связью, построенный на основе порождающего

полинома P(x) и выполняющий операцию деления F′(x)/P(x), “порождает”

последовательно столбцы проверочной матрицы )x(H

n,l

при поступлении каждой

кодовой последовательности и одновременно производя суммирование по

модулю два символов столбцов, соответствующие ненулевым символом входной

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

5. Из равенства F′(x)·H

(x)=0 следует, что для каждой фиксированной

кодовой последовательности сумма некоторого подмножества столбцов

проверочной матрицы равно нулю.

Например, для матрицы

H(x)=













(2.27)

кодовая последовательность F′(x)=100101 является кодовой последовательностью

(n,k,

)=(6,3,3)- кода.

При матричном умножении согласно равенствам F′(x)·H

(x)=0 или

(x)·H(x)=0, т.е. F′(x)·H

(x)=0, ненулевые символы этой последовательности, т.е.

F′(x)=100101, “отсеивают”: 1-й; 4-й и 6-й столбцы матрицы H(x), т.е.

























⊕













⊕













Поскольку аналогичное соотношение должно выполняться для любого

кодового слова, то можно заметить следующее:

а) если кодовое расстояние равно

d , то должно существовать по крайней

мере одно подмножество, состоящее из

d столбцов матрицы H(x), сумма которых

равна “0”;

б) если рассматривать столбцы матрицы H(x) как вектор, то можно сказать,

что для кода с кодовым расстоянием

d подмножества из (

d -1) столбцов матрицы

H(x) должны быть линейно независимы.

Последнее свойство СЛБК (точнее утверждение) составляет одну из

фундаментальных теорем о групповых кодах. Кроме того, это утверждение

позволяет находить

d группового кода по заданной матрице H(x), а также

строить H(x), приводящие к кодам с гарантированным значением

d .

Так рассматривая матрицу (2.27) (n,k,d

)=(6,3,3) кода, видим, что все столбцы

матрицы H(x) различны, так что сумма по модулю два двух любых столбцов

никогда не равна нулю. С другой стороны, существует по крайней мере одно

множество из трех столбцов, например, состоящее из столбцов 1, 2 и 5, сумма

которых равна “0”, таким образом,

d =3.

Из указанного свойства вытекает способ, с помощью которого была получена

граница Гильберта для

, а именно:

−

∑

−

C .

Предположим, что мы хотим построить (n,k)—код с некоторым значением

d , то необходимо поступить следующим образом:

– возьмем в качестве первых двух столбцов H(x) произвольные векторы,

состоящие из “0” и “1” и длиной равной l=(n-k) двоичных символов, с

выполнением одного условия, а именно, чтобы они были различными;

– выберем третий столбец, т.е. вектор H(x), так чтобы он не являлся

линейной комбинацией первых двух столбцов;

– продолжая таким образом, будем выбирать каждый следующий столбец,

так чтобы он не был линейной комбинацией никаких (

d -2) или меньшего числа

выбранных столбцов;

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

комбинации

d -2 или меньшего числа уже выбранных столбцов. В наихудшем

случае все эти линейные комбинации являются различными ненулевыми

векторами. Тогда перед последним шагом должно выполняться неравенство вида

12C...CC

−〈+++

−

−−−

, позволяющее добавить к матрице H(x) еще один

столбец.

Теперь рассмотрим обратную задачу, а именно:

-из матричного представления СЛБК можно получить выражение (равенства

и неравенства), связывающие параметры кода, т.е. n;k;

d ; хотя порой эти

равенства и неравенства могут быть не очень точными.

Следующая теорема (теорема Синглтона) накладывает ограничения на

возможные значения параметров (n,k,

d )- кода: минимальное кодовое расстояние

(минимальный вес) любого (n,k)- кода удовлетворяет неравенству:

≤ n-k+1.

Доказательство состоит в следующем: ненулевое кодовое слово (кодовая

последовательность) минимального веса в (n,k)- коде имеет вес

d , т.е.

0кс

d≥ω .

Существует слово систематического кода с одним ненулевым информационным

символом и (n-k)=l проверочными символами. Такое кодовое слово не может

иметь вес, больший чем (l+n-k).

Следовательно, минимальный вес кодового слова не может быть больше чем

(l+n-k).

Любой (n,k) – код с минимальным расстоянием, удовлетворяющим равенству

d =l+n-k, называется (n,k) – кодом с максимальным кодовым расстоянием.

Данная граница (граница Синглтона) показывает, что для исправления

.ош

(n,k) – кодом данный код должен иметь не менее l

.ош

t2⋅≥ проверочных символов,

т.е. два проверочных символа на одну ошибку.

Примечание: большинство помехоустойчивых кодов, даже оптимальные,

имеют намного больше проверочных символов, чем требует граница Синглтона,

но параметры некоторых кодов точно удовлетворяют границе l

.ош

t2⋅=

двоичных

символов. В частности, коды с максимальным, минимальным кодовым

расстоянием равным

d =l+n-k имеют точно l

.ош

t2⋅= проверочных символов.

В соответствии с классификацией групповых блоковых кодов (рис. 2.1) к

данным кодам относятся: дуальные коды, эквивалентные коды, полиномиальные

коды, итеративные коды, коды произведения, коды максимальной длины,

транспарантные коды, ортогональные коды, биортогональные коды и др. Кратко

рассмотрим их сущность.

2.6. Дуальные коды: определение и общая характеристика

Если =)x(G

n,k

[ )x(I

k,k

: )x(P

,k l

] есть порождающая матрица, а

=)x(H

n,l

[– )х(P

k,l

)x(I

kn−

] - проверочная матрица и где:

−)x(I

k,k

информационная подматрица рангом (k

k),

−)x(P

,k l

проверочная подматрица рангом k

−

транспонированная проверочная подматрица рангом l

то рассматривая эти матрицы можно сделать вывод [1…4]:

- каждая из них содержит множество линейно-независимых кодовых

векторов и, следовательно, каждая из матриц может рассматриваться как базис

некоторого линейного пространства. Кроме того, каждое из этих пространств

является подпространством векторного пространства, состоящего из всех наборов

длины “n” двоичных символов. Скалярное произведение каждой строки матрицы

(x) на каждую строку H(x) равно нулю, т.е. H(x)* G

(x)=0.

Следовательно, можно “поменять ролями” эти две матрицы, т.е. H(x)-

использовать как порождающую, а G(x)- как проверочную матрицу некоторого

другого кода.

Коды, связанные таким образом, называются дуальными кодами или

дуальными друг другу.

Векторное пространство, соответствующее матрице H(x), будет называться

нулевым пространством для векторного пространства, соответствующего матрице

G(x), поскольку все векторы из одного пространства ортогональны всем векторам

из другого пространства.

Например, коды Хэмминга являются нулевыми пространствами для так

называемых кодов максимальной длины (КМД).

Если задан или получен некоторый групповой линейный код, например, код

Хэмминга длиной n=2

-1 двоичных символов с P(x)=X

l-1

+…+1 (порождающий

полином), то дуальный код той же длины, т.е. n=2

-1 двоичных символов,

получается, если взять в качестве порождающего полинома P(x) его проверочный

полином h(x), т.е. h(x)=P(x)=

)x(P

−

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

построения формирователя проверочных символов кодера (ФПСк), содержащего

“k” ячеек памяти. Таким образом, дуальный код – это код, который имеет такую

же длину “n” как и код с образующим полиномом P(x), но у которого в качестве

проверочного полинома берется образующий полином, т.е. h(x)=P(x).

Дуальный код имеет следующие параметры: (

0д0дд

d,,2()d,k,n l

= ). Так,

например, для кода Хэмминга с параметрами (n,k,

)=(7,4,3) и

P(x)=x

+x+1,получаем дуальный код с h(x)=P(x)=

)x(P

+x+1 с ФПСк,

имеющего следующее построение (рис. 2.2)

Рис.2.2. Функциональная электрическая схема дуального ЛБК

ФПСк работает следующим образом: в начальный момент времени ключ К1

находится в положении “1”, а ключ К2–разомкнут и в регистр сдвига ФПСк

записываются четыре информационных символа. Затем ключ К1 устанавливается

в положение 2 (цепь обратной связи замкнута), а ключ К2 замыкается и в течение

(n+1)=(7+1)=8 тактов осуществляется сдвиг информационных символов с

одновременным формированием проверочных символов; в течение k=l=4 такта в

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

код с h(x)=P(x)′=x

+x+1 будет иметь следующие параметры: (n,k,d

)=(2

4-1

)=(8,4,4).

2.7. Эквивалентные коды: определение и общая характеристика

В соответствии с [3] используется несколько определений данным кодам,

например, следующие два:

1.Эквивалентные коды—это двоичные линейные блоковые коды длины

−

двоичных символов с проверочной матрицей

)x(H

n,l

и с равной

Вых.

Q(x)

Вых.

F(x)

корректирующей способностью, отличающиеся только перестановкой столбцов

этой матрицы, а каждый столбец этой матрицы является двоичным вектором

длины l двоичных символов. (Однако с инженерной точки зрения эквивалентные

коды далеко не равноценны, так как процедуры кодирования и декодирования их

могут существенно отличаться сложностью реализации);

2. Второе определение данных кодов является более коротким, а именно:

эквивалентными кодами называются ЛБК одинаковые с точностью до

перестановки координат.

Суть их такова: из (n,k)—кода с

можно получить новый (n′,k′)—код, т.е. с

теми же параметрами, если в каждом кодовом слове выбрать позиции и поменять

местами символы в этих позициях. Этот новый код лишь тривиальным образом

будет отличаться от исходного. В этом случае говорят, что такой код

эквивалентен исходному (n,k)—коду.

Порождающие матрицы G(x) и G′(x) эквивалентного кода имеют простую

связь друг с другом. Сам эквивалентный код является пространством

(совокупностью) строк матрицы G(x) и остается неизменным при выполнении

элементарных операций над строками.

Перестановка координат кода эквивалентна перестановке столбцов в матрице

G(x). Следовательно, два (n,k)—кода эквивалентны тогда и только тогда, когда их

порождающие матрицы получаются одна из другой посредством:

а) перестановкой столбцов;

б) элементарных операций над строками.

Каждая порождающая матрица G(x) эквивалентна некоторой матрице

канонического ступенчатого вида, и, поскольку строки G(x) линейно независимы,

все строки эквивалентной матрицы являются ненулевыми. Следовательно, с

точностью до перестановки столбцов любая порождающая матрица эквивалентна

матрице, которая в первых “k” столбцах содержит единичную подматрицу рангом

k).

Эквивалентную матрицу можно записать в виде: G″(x)=[IMP], где Р– есть

подматрица рангом k

(n-k).

Любая порождающая матрица может быть приведена к такому частному

виду G″(x) при помощи последовательности элементарных операций над

строками и последующей перестановкой столбцов.

Такую порождающую матрицу называют порождающей матрицей в

систематическом виде.

2.8. Коды максимальной длины или коды m-последовательностей:

определение и общие сведения

Коды максимальной длины (КМД) дуальны кодам Хэмминга и обладают

следующими свойствами [2]:

1. Регистр сдвига с “l” ячейками памяти имеет только

−

ненулевых

состояний, так что длина максимального цикла равна L=

−

двоичных символов,

а так как длина кода также равна n=

−

, то каждое кодовое слово является

выходной последовательностью максимальной длины;

2. Кодер, т.е. ФПСк, проходит за один цикл через все

−

ненулевых

состояний. Поэтому все

−

ненулевых кодовых последовательностей (кодовых

слов) являются циклическими кодовыми сдвигами одного ненулевого кодового

слова и, следовательно, все ненулевые кодовые слова имеют один и тот же вес,

кс

ω ≥d

; такой код называется эквидистантным или симплексным кодом;

3. Вес каждого ненулевого кодового слова

кс

составляет

кс

−

и весовая

функция будет иметь вид:

x)12(1)x(A

−

⋅−+=

Эта весовая функция связана с весовой функцией кода Хэмминга

тождеством:

)]x1/()x1[(A)x1(2)x(B

+−⋅+=

−

КМД или коды m—последовательностей на практике используются для

построения шумоподобных сигналов (ШПС), испытательных сигналов, т.е.

псевдослучайных последовательностей (ПСП), в системах с расширением спектра

и т.д.

2.9. Транспарантные коды: определение и общие сведения

Транспарантные коды — это такие помехоустойчивые коды, у которых

кодовыми словами являются как прямые (

2)x(F =

) кодовые слова (кодовые

последовательности), так и инверсные последовательности. Для того, чтобы в

коде содержались как прямые, так и инверсные последовательности необходимо,

чтобы в коде было слово, состоящее из логических 1 (для выполнения аксиомы

замкнутости), а тогда, исходя из основного уравнения кодирования следует, что

количество логических 1 каждой строке проверочной матрице должно быть

четным.

Полные коды Хэмминга с d

=3 и 4 содержат в каждой строке Н(х) четное

число “1” и, следовательно, эти коды Хэмминга относятся к транспарантным

кодам. Укороченные коды такого типа с d

=3 существуют и имеют d

=4, а длина

кода “n” должна быть четной.

Пример. Пусть имеем полный код Хэмминга (n,k,d

)=(32,26,4), а надо

получить код с k=1, т.е. с Т=5 (Т—трансплантация кода). В этом случае длина

кода равна n′=n-T=32-5=27 двоичных символов. Следовательно, такого кода не

существует. Имеется два пути обеспечения “k”:

– первый путь—увеличение “k” на единицу;

– второй путь—увеличение “l” на единицу, оставив “k”=const.

2.10.Ортогональные коды: определение и общие сведения

Ортогональные коды являются разновидностью (подклассом) кодов

максимальной длины, которые получаются путем расширения данных кодов за

счет введения общей проверки на четность.

Ортогональные коды имеют длину

двоичных символов (l—длина

столбца матрицы) и вес каждого ненулевого кодового слова равен

−

==ϖ

Следовательно, любые два кодовых слова будут совпадать в 2

1−l

позициях и

различаться в 2

1−l

позициях.

Использовав этот код с противоположными сигналами, получим множество

из

ортогональных сигналов (отсюда название “ортогональный код”).

Примером ортогональных сигналов и ортогонального кода являются ФМ—

сигналы (0→0º,11→180º), ДФМ (00→0˚, 11→180˚) ТФМ и т.д.

2.11. Биортогональные коды: определение и общие сведения

Биортогональные коды являются расширением ортогональных кодов путем

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

ортогональных сигналов. Таким образом, получим множество биортогональных

сигналов для кодовых векторов или кодовых последовательностей.

Биортогональный код может быть сформирован из кода Рида-Маллера

первого порядка, в свою очередь сформированного из ортогонального кода путем

добавления кодового слова (кодовой последовательности) состоящего целиком из

логических 1.

Характеристики ортогональных и биортогональных кодов очень близки к

характеристикам КМД. Однако в когерентных системах связи чаще всего

используют биортогональные коды, поскольку они обладают некоторыми

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

биортогональных кодов, как и КМД, является их высокая избыточность, т.е.

низкая скорость передачи: (R<0,5).

Контрольные вопросы и задачи

1. Дать определение групповым двоичным линейным кодам. Основные

свойства данных кодов.

2. Пояснить сущность и назначение порождающей G(x) и проверочной H(x)

матриц. Основные свойства данных матриц.