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

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

В общем можно отметить, что в теории и технике (практике)

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

1) построение кода, разработка способа кодирования и его реализация;

2) аналогично, по отношению алгоритма декодирования кода.

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

обеспечивающий выполнение выбранных критериев качества помехоустойчивого

кодирования.

Во втором случае - разработать алгоритм декодирования, обеспечивающий

максимальный энергетический выигрыш кодирования (ЭВК) при минимальной

сложности реализации декодера.

1.4. Места включения кодера и декодера в тракте передачи данных

Традиционно основные функции цифровой системы связи или тракта

передачи данных (ПД) принято подразделять в соответствии со следующей

структурной схемой(рис.1.1):

Рис.1.1. Структурная схема тракта передачи данных

Данные, поступившие от источника информации (ИИ), прежде всего,

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

представления данных (сжатие информации). Это промежуточное представление

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

источника. Затем данные обрабатываются кодером канала, преобразующий

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

ИИ

кодер

источн.

кодер

канала

Пол.Ин.

декодер

канала

декодер

источн.

DEMOD

MOD

непрерыв.

кан. св.

цифровой тракт ПД

канал ПД

ДКС

последовательность, называемую кодовым словом канала. Кодовое слово канала

представляет собой новую более длинную последовательность с большей чем у

кодового слова источника избыточностью. Каждый символ кодового слова канала

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

бит. Далее модулятор (MOD) преобразует каждый символ кодовой

последовательности канала в соответствующий аналоговый сигнал из конечного

множества допустимых аналоговых сигналов. Последовательность аналоговых

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

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

связи (проводные каналы связи, РРЛ, ССС и т.д.). На приемной стороне обработка

информации производится в обратном порядке. Далее будем рассматривать

вопросы, касающиеся только кодера и декодера.

1.5. Сущность принципа помехоустойчивого кодирования

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

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

сообщения, либо ввести дополнительную (избыточную) информацию в

передаваемое сообщение.

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

образом, избыточной информации в передаваемые сообщения.

Простым методом введения избыточности в передаваемые сообщения

является метод "γ" (γ≥3) - кратной передачи либо каждого информационного

символа, либо всего блока в целом. Решение о каждом принятом

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

Например:

подсчет двоичных

символов одинако-

вой полярности или

знака

1 0 1 1 0 – передаваемое сообщение,

1 0 0 1 0 – принятое сообщение при первой передаче,

1 0 1 0 0 – повторная передача,

0 0 1 1 0 – третья передача,

1 0 1 1 0 – восстановленное сообщение.

Таким образом, в результате 3-х кратной передачи блока из 5-ти двоичных

символов была обнаружена и исправлена одиночная ошибка (3-й двоичный

символ). Достоинством такого метода кодирования информации является его

простота, а недостатком высокая избыточность информации; r = 66%.

1.6. Определение кода и способа помехоустойчивого кодирования.

Основные характеристики кодов

Существует и используется много определений коду и помехоустойчивому

кодированию. Например, код есть форма представления информационного

сообщения, не зависящая от его физической сущности или код представляется

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

введены корреляционные связи или код есть конечное множество кодовых

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

алгоритму или правилу. Помехоустойчивое кодирование представляет собой

процесс преобразования передаваемых информационных символов по

определенному алгоритму или по определенным правилам, и в результате чего

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

передаваемые информационные сообщения. В общем помехоустойчивое

кодирование основывается на введении избыточной информации в передаваемые

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

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

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

делятся на разрешенные и запрещенные и по которым затем по определенным

алгоритмам обнаруживаются и корректируются ошибочные информационные

символы.

Основными характеристиками помехоустойчивых кодов являются [1...4]:

1. Основание кода (q) - определяется числом (количеством) различных

единичных элементов (символов), используемых при построении кода и кодовых

последовательностей. Основание кода чаще всего обозначается через "q" и при

этом:

)kn(

−

%100*)n/(n/)kn(r l

−

- если q=2, т.е. используются двоичные символы "1" и "0", то такие коды

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

GF(q)=GF(2);

- если q>2, например, q=2

, m≥2, то такие помехоустойчивые коды называются

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

Галуа, т.е. GF(q

)=GF(2

);

2. Длина кодовой последовательности (n) - равна количеству двоичных

символов (бит) в данной кодовой последовательности. Длину кодовой

последовательности принято обозначать через "n": минимальная длина кодовой

последовательности n=2 двоичным символам (нижний предел); верхний предел

"n" в принципе может достигать тысячи и десятки тысяч двоичных символов;

3. Количество информационных символов (k) - это количество двоичных

символов несущих полезную информацию; количество информационных

символов в кодовой последовательности принято обозначать через "k" и их число

может быть равным k=l,2,.. и т.д. двоичных символов;

4. R=k/n скорость передачи кода, характеризует количество избыточных

символов приходящиеся на один информационный символ. Чем больше R, т.е.

R→1 (R всегда меньше 1), тем эффективнее помехоустойчивый код, так как

передается меньше избыточной информации;

5. Избыточность помехоустойчивого кода делится на:

- абсолютную избыточность двоичных символов;

- относительную избыточность ;

6. Вес кодовой последовательности (w

к.посл.

) – определятся количеством

ненулевых символов, входящих в кодовую последовательность. Например, пусть

n=10 двоичных символов, а две кодовые последовательности данного

помехоустойчивого кода имеют следующую структуру: F

(x)= 1001110010 и

(X)=0010101100, то вес F

(x) w

=5, a F

(x) – w

=4;

7. Классификация кодовых последовательностей: если заданы или известны

такие характеристики помехоустойчивого кода как n и k, то можно определить:

- К

общ

- общее количество кодовых последовательностей,

- К

раз

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

- К

запр

- количество запрещенных кодовых последовательностей.

В принципе из общего количества К

общ

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

некоторые кодовые последовательности будут иметь одинаковый вес, а их общее

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

необнаруживаемые ошибки данным кодом;

8. Кодовое расстояние (d) - равно (соответствует) количеству позиций которыми

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

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

путём суммирования по модулю два, например,

1001110010

(x) ⊕ F

(x)= ⊕

0010101100

d=1 11 1111 =7, т.e. d =7.

Так как общее количество кодовых комбинаций К

общ

, то общее число

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

/2, среди которых d может быть как

максимальным, так и минимальным.

Хэмминг доказал, что не максимальное, а минимальное кодовое расстояние

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

кодовое расстояние обозначается как d

или d

(хэмминговое расстояние) и равно

наименьшему значению d из всей их совокупности. Например, d

=7, d

=5, d

=8,

…, d

=3, d

i+1

=4, …, d

=9, …, d

=3.

Замечание: с позиции теории кодирования d

показывает, сколько символов в

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

кодовую последовательность. Кодовое расстояние может обозначаться как

dist(F

), например, dist(0122,2102)=2.

Хэмминговое расстояние (d

) чаще всего используется при передаче

информации в дискретном канале связи, т.е. при передаче информации на

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

В канале связи с многократной ФМ (МФМ) хэмминговое расстояние не в

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

пары фаз "0", "π/2" и "0", "3π/2" дают одинаковое фазовое различие, равное π/2.

Для канала связи с МФМ используется расстояние Ли,

∑

−

iЛ

измеряемое как , где а

– разность значений символов, находящихся в i-позиции

двух сигналов одинаковой длины "n": a

= a′

, при 0 ≤ a

≤ (q+1)/2 и a′

= q-a

, при

(q+1)/2 < а

≤ q-1.

Например, для двух кодовых слов с набором фаз символов 0000 и 0, π/2, π,

3π/2 или после замены фаз числами 000 и 0123, d

=0+1+2+1=4, а d

=3. При q=2 и 3

значения d

и d

совпадают. Наибольшему расстоянию d

, так же как и d

соответствуют противоположные сигналы с фазами 0000 и ππππ.

Кроме кодовых расстояний Хэмминга (d

) и Ли (d

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

используются кодовые расстояния Евклида (d

) и Бхаттачария (d

). Кодовое

расстояние Евклида (d

) используется для оценки расстояний двух сигналов

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

непрерывному каналу связи. Кодовое расстояние Бхаттачария (d

) характеризует

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

(сигналов) слов помехоустойчивого кода. Далее будем пользоваться только

хэмминговым расстоянием (d

Определены как нижние, так и верхние границы значений d

- нижние границы устанавливают факт существования помехоустойчивых

кодов с таким значением d

;

- верхние границы определяют максимальное теоретическое значение d

Из нижних границ наиболее известна и находит широкое применение

граница Варшамова-Гильберта

, (1.1)

где d

min

- максимальная величина, удовлетворяющая этому неравенству.

Для q=2 выражение (1.1) принимает вид

∑

−

<−

knin

min

q)1q(*)(

. (1.2)

Из нескольких известных верхних границ хорошие результаты при

R≥0,5...0,6 дает граница Хэмминга

, где t = (d

-1)/2. (1.3)

Если R<0,4...0,5 , предельное значение d

min

определяется простой и

достаточно грубой граничной оценкой Плоткина

min

≤ [(q-1)*(n*q

k-1

]/(q

k-1

). (1.4)

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

d ≤ n-k+1, (1.5)

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

9. Кратность (количество) исправляемых и обнаруживаемых ошибок.

Если некоторый помехоустойчивый код с параметрами q=2, "n" и "k"

используется для передачи информации, то К

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

длины "n" двоичных символов образуют информационную часть кодового

пространства или множества, а остальные К

=К

n-k

- образуют ложную часть

кодового множества, что условно можно представить так (рис.1.2).

Рис.1.2. Подпространства множества кодовых последовательностей (n,k)–

кода

Разделение кодового множества на информационную и ложную части

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

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

∑

−

knn

2)(

∑

−

<−

knin

min

q)1q(*)(

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

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

- истинной или без ошибок; либо ошибки просто не обнаружены кодом.

Для того чтобы исправить ошибки, полное кодовое множество разбивают на

информационных частей, взаимно однозначно соответствующих

информационным последовательностям, что условно можно представить так:

Принятое кодовое слово при сопоставлении с кодовым множеством может

оказаться в одной из его частей: если оно будет в части, соответствующей этому

слову, например, ξ, то получателю информации выдается истинное слово, а если

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

его надо исправить, т.е. скорректировать ошибку.

Если же в этом кодовом множестве выделить три части (групп) кодовых

последовательностей, например, ξ (ошибок нет), i (есть корректируемые ошибки)

и γ (некорректируемые ошибки) (рис.1.3),

Рис.1.3. Условное представление подпространств кодовых последователь-

ностей: при отсутствии ошибок (ξ ), корректируемые ошибки (i) и

некорректируемые ошибки (γ)

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

некорректируемыми ошибками.

Как уже отмечалось выше, Хэмминг доказал, что корректирующие свойства

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

Хэмминг доказал следующее: если две кодовые последовательности отличаются

друг от друга в t (t≥1) позициях (разрядах, символах), а от всех остальных

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

чем в t позициях, то для коррекции t ошибок необходимо чтобы минимальное

кодовое расстояние должно быть d

≥2*t+1(2).

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

исправил t ошибок необходимо, чтобы минимальное число позиций которыми бы

отличались любые две кодовые последовательности рассматриваемого

помехоустойчивого кода составляло бы d

≥2*t+1(2) позиций.

Если выполняется такое условие, то помехоустойчивый код может

исправить

)2(1d

исп

−

≤

ошибочных символов, либо обнаружить t

обн

≤ d

–1

ошибочных двоичных символов; число 2 вычитается при четном значении d

Сказанное последнее можно проиллюстрировать следующими рисунками

Рис.1.4. Условное расположение кодовых последовательностей для разных

значений d

(x), n

≥

2*t+1(2)

а)

1(2)d

исп

−

≤

обн

≤

-1

≥

t+1

б)

(x)

в)

(x)

Помехоустойчивый код не

обнаруживающий и не ис-

правляющий ошибок

Для первого случая (рис.1.4а) расположения кодовых последовательностей

следует, что если кодовая последовательность F

(x) отстоит от кодовой

последовательности F

(x) на расстоянии d

двоичных символов, то это означает,

что в кодовой последовательности F

(x) необходимо заменить d

кодовых

символов на обратные, чтобы получить кодовую последовательность F

(x),

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

(x).

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

меньшем расстоянии чем d

, т.е. они будут иметь более чем d

совпадающих

(одинаковых) кодовых символов, то декодер не обнаружит и не исправит ошибки

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

(x); случай (рис.1.4в).

Если же две кодовые комбинации будут находиться на расстоянии d

≥t+1, то

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

является ошибочной- случай (рис.1.4б).

Для того, чтобы помехоустойчивый код исправлял t

исп

ошибок и

обнаруживал t

обн

ошибок необходимо, чтобы d

≥ t

исп

+ t

обн

+ 1.

Рассмотрев принятые условные обозначения основных характеристик

помехоустойчивого кода и их сущность, можно записать общее обозначение

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

например, так (n,k,d

)=(l5,7,5). Такая запись помехоустойчивого кода говорит о

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

10. Вероятность ошибочного декодирования группового линейного

существенно зависит от типа кода, его параметров и типа канала связи. Для

двоичного симметричного канала связи без памяти вероятность определяется по

формуле

∑

−

1ti

ini

nош

исп

q*P*CP

. (1.6)

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

К настоящему моменту времени разработано большое количество классов

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