Классификация помехоустойчивых кодов

ИЗБЫТОЧНЫЕ КОДЫ

БЛОЧНЫЕ

НЕПРЕРЫВНЫЕ

(СВЕРТОЧНЫЕ)

РАЗДЕЛИМЫЕ

ЛИНЕЙНЫЕ

НЕЛИНЕЙНЫЕ

ИТЕРАТИВНЫЕ

ЦИКЛИЧЕСКИЕ

ХЭММИНГА

НЕРАЗДЕЛИМЫЕ

С постоянным весом

В блочных кодах информационная последовательность на входе кодера разбивается на отдельные блоки, которые кодируются и декодируются независимо друг от друга. Блочные коды являются равномерными, то есть все блоки содержат одинаковое число элементов кода.

В непрерывных (древовидных) кодах передаваемая последовательность образуется без предварительного разбиения информационной последовательности на независимые блоки. Процессы кодирования и декодирования являются непрерывными. Проверочные символы размещаются между информационными по определенному алгоритму. Часто последовательность на выходе кодера вообще нельзя разделить на информационные и проверочные символы. При этом каждый информационный символ влияет на формирование нескольких десятков символов выходной последовательности.

Блочные коды делятся на разделимые и неразделимые в зависимости от метода введения избыточности. В разделимых кодах информационные элементы обычно размещаются в начале слова. Проверочные элементы вычисляются по определенным правилам и размещаются обычно в конце кодового слова. В неразделимых кодах символы кодовых слов не делят на информационные и проверочные. К таким кодам относятся коды с постоянным соотношением нулей и единиц в кодовых словах. Например, при связи по коротковолновым радиоканалам используется 7-ми элементный равновесный код. Из общего числа N₀=2⁷=128 кодовых слов используется только N=35 слов равного веса , каждое из которых содержит 4 нуля и 3 единицы.

Разделимые двоичные коды делятся в свою очередь на линейные и нелинейные.

Линейными кодами называются коды, в которых сумма по модулю 2 двух или более разрешенных кодовых слов дает другое разрешенное кодовое слово.

Нелинейные коды этим свойством не обладают. К ним относятся итеративные коды. Итеративные коды – это коды с контрольным суммированием, причем каждое кодовое слово участвует в нескольких системах проверок.

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

№6

Линейные коды

Блочным линейным кодом называется (n,k) код, проверочные символы которого являются линейными комбинациями информационных символов. Здесь:

n – длина кода, то есть длина кодовых слов

k – число информационных символов

Обозначим U – последовательность из k информационных символов.

U=(u₁, u₂,…….u_k)

Обозначим V – кодовое слово линейного кода длиной n символов.

V=(v₁, v₂,……….v_n)

К одовое слово V формируется из последовательности U по следующему правилу:

Коэффициенты _l,i представляют собой фиксированные двоичные символы, не зависящие от u .При выборе разных совокупностей _l,i получаются различные линейные коды.

Отношение R=k/n называется скоростью кода, а величина W=1-R – называется избыточностью кода.

Линейный код может быть задан в виде таблицы кодовых слов или при помощи указания коэффициентов _l,i . Второй способ более экономичен.

П ри задании линейного кода с помощью набора коэффициентов _l,i записывается образующая матрица G . Матрица G имеет размер kxn . Первые k столбцов представляют собой единичную матрицу kxk , следующие n-k столбцов представляют совокупность коэффициентов _l,i (матрица проверочных элементов).

Это запись образующей матрицы в канонической форме.

В строке матрицы проверочных элементов должно быть не менее чем (d_min-1) единиц, а расстояние Хэмминга между строками не менее (d_min-2), где d_min - кодовое расстояние.

При заданной информационной последовательности и образующей матрице кодовое слово V получают следующим образом

V_i=U_i при 1<=i<=k

и

V_i=U₁*_1,i  U₂*_2,i  ….  U_k*_k,i при k+1<=i<=n

Пример

П усть разделимый линейный код (5,3) задан при помощи образующей матрицы G

Запишем в виде формул процедуру нахождения символов кодового слова, если задана некоторая информационная последовательность U=(u₁,u₂,u₃). Кодовое слово будет содержать 5 символов V=(v₁,v₂,v₃,v₄,v₅).

Если в информационной последовательности имеется только один символ 1 на j – ой позиции, а на остальных позициях находятся нули U=(000….1_j….0), то соответствующее кодовое слово V будет представлять собой j – ю строку матрицы G. Обозначим j – ю строку матрицы G, как g_j. Произвольное кодовое слово можно представить в виде суммы по модулю 2 строк образующей матрицы с номерами j ,значения которых совпадают с номерами ненулевых разрядов в информационной последовательности.

Вернемся к примеру, приведенному выше. Пусть U=(101), тогда V=(10111), кодовое слово получилось как сумма по модулю 2 первой и третьей строк образующей матрицы.

Свойства линейных кодов

1. Любые К линейно-независимых кодовых слов задают все множество 2^к слов линейного кода и могут составить его образующую матрицу. Произвольная образующая матрица может быть приведена к каноническому виду суммированием строк по mod2.

К одовые слова V_j являются линейно-независимыми, если сумма по модулю 2 вида

только когда все коэффициенты _j равны 0.

2. Сумма по модулю 2 любого числа кодовых слов также является словом данного линейного кода.

3. Нулевая последовательность всегда является кодовым словом.

4. Кодовое расстояние d_min равно минимальному весу ненулевого кодового слова.

5. И з любого линейного (n,k) кода с кодовым расстоянием d_min можно получить код (n-i, k-i) с кодовым расстоянием не меньше d_min . Для этого из образующей матрицы G исходного кода вычеркивают любые i строк и i, ставших нулевыми столбцов. Например, задан код (5,3) с образующей матрицей G, кодовое расстояние которого равно d_min=2.

П олучим укороченный код (4,2), вычеркнув первую строку и первый столбец, ставший нулевым, в матрице G. Образующая матрица укороченного кода G' имеет вид

Кодовое расстояние укороченного кода d_min=2.

Задача 1

Образующая матрица линейного кода имеет вид

К акие из приведенных последовательностей являются кодовыми словами данного кода?

1. 1000

2. 100011

3. 10101

4. 11011

5. 00000

Задача 2

К акие из приведенных матриц являются образующими матрицами линейного кода (5,3)?

Лекция 8

ДЕКОДИРОВАНИЕ ЛИНЕЙНЫХ КОДОВ

П роцедура декодирования линейного разделимого кода состоит в проверке соотношения

Эти уравнения можно решить при помощи проверочной матрицы Н. В случае правильного приема V*H=0.

П роверочная матрица имеет размеры nx(n-k) и имеет вид

Д ля кода (5,3) с порождающей матрицей G

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

Произведение принятой последовательности Y и проверочной матрицы называется синдромом S.

S=Y*H

С индром – это строка, которая содержит r=n-k элементов. Синдром равен 0 (все элементы синдрома равны 0), если ошибки в принятом кодовом слове отсутствуют, то есть S=V*H=0. Если принятый i-й проверочный символ (1<=i<=r) отличается от i-го проверочного символа, вычисленного по принятым информационным символам по известным правилам, то i-й элемент синдрома будет равен 1.

З десь e – комбинация или вектор ошибки. Вид синдрома зависит от вида вектора ошибки. Один и тот же синдром соответствует 2^k векторам ошибок. Некоторый вектор ошибки e' имеет тот же синдром, что и вектор e, если

Декодирование с исправлением ошибок

При декодировании с исправлением ошибок каждому синдрому линейного кода ставят в соответствие определенный вектор ошибки, который является наиболее вероятным в заданном канале. Например, если задан двоичный симметричный канал без памяти ДСК, то в таблицу декодирования линейного кода следует включить вектора ошибок с минимальным весом.

Декодирование с обнаружением ошибок

В данном случае при приеме последовательности Y вычисляется синдром и выдается сигнал наличия ошибки, если S не равен нулю. Если вектор ошибки совпадает с одним из кодовых слов, ошибка не может быть обнаружена.

Определим вероятность необнаруженной ошибки для ДСК

P(0/0)=P(1/1)=1-  - вероятность правильного приема двоичного символа в ДСК

P(0/1)=P(1/0)=  - вероятность ошибки в двоичном символе

Д ля ДСК без памяти вероятность появления любого вектора ошибок веса t в кодовом слове длиной n символов равна

Л инейный код не обнаружит ошибку, если вектор ошибки совпадет с каким-либо кодовым словом. Поэтому, для вычисления вероятности необнаруженной ошибки необходимо знать спектр весов кода. Спектром весов кода называется последовательность чисел N(t), каждое из которых показывает число кодовых слов, содержащих t единиц.

Задача

Задана проверочная матрица линейного кода

К акие из перечисленных комбинаций являются кодовыми словами данного кода:

Y₁=01111 +

Y₂=111000

Y₃=11011

Y₄=1011

Y₅=10110 +

Задача

Задан код с длиной кодового слова n=12. Определить необходимое минимальное число проверочных символов, если код должен исправлять все одиночные ошибки?

В соответствии с условием задачи число одиночных ошибок в кодовом слове равно 12. Каждой комбинации ошибки должен соответствовать свой синдром. Длина синдрома составляет (n-k) символов, число синдромов – 2^n-k. Число ненулевых синдромов должно быть не менее n=12, то есть

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