N=N0. Здесь n – число кодовых слов, используемых для передачи сообщений. Такой код называется простым icon

N=N0. Здесь n – число кодовых слов, используемых для передачи сообщений. Такой код называется простым


Смотрите также:
Объектно-ориентированное программирование...
Основные сведения...
Фонетическая транскрипция...
Лекция 10. Передача данных по каналу связи Вданном разделе рассматриваются вопросы передачи...
Выложенный здесь перевод можно назвать переводом разве что условно...
Программа-минимум по специальности 05. 12. 13 «Системы...
Сочинение ученицы 11 класса Гончаровой Елены...
Лекция понятие о колебаниях. Периодический процесс...
Программа для трансляции в байт-код называется javac exe Программа для выполнения байт-кода...
Решение. Частичная сумма этого ряда...
Как видно из схемы, число двоичных разрядов, используемых в процессе преобразования...
Программа для студентов 3 курса, обучающихся по специальностям...



Загрузка...
скачать
КОДИРОВАНИЕ С ЦЕЛЬЮ ПОВЫШЕНИЯ ВЕРНОСТИ ПЕРЕДАЧИ

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

Пусть для передачи сообщений используется равномерный двоичный код с длиной кодового слова n. Тогда общее число кодовых слов равно N0=2n. Предположим, что для передачи сообщений используются все возможные кодовые слова N=N0. Здесь N – число кодовых слов, используемых для передачи сообщений. Такой код называется простым или примитивным.

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

Увеличим длину кодовых слов n. Тогда общее число кодовых слов N0 будет больше числа слов, используемых для передачи сообщений N.

N0>N

Выбранные для передачи кодовые слова (их число равно N) называются разрешенными. Остальные кодовые слова, которые не используются и в точке приема появляться не должны, называются запрещенными.

В этом случае ошибки могут привести к появлению в приемнике либо разрешенного кодового слова (ошибка не обнаружена), либо запрещенного кодового слова (обнаружено наличие ошибок).

^ Рассмотрим несколько примеров.

  1. Для передачи сообщений используется простой код.

А
Кодовые слова отличаются друг от друга в одном либо двух символах.

^ Число символов, в которых одно слово отличается от другого, называется расстоянием Хэмминга.


00

В

01

C

10

D

11

Наименьшее расстояние между словами кода называется кодовым расстоянием dmin.

Для данного кода расстояние Хэмминга d=1 или 2, а dmin=1.

Любая одиночная или двойная ошибка приводит к замене одного разрешенного кодового слова другим, и факт ошибки в приемнике обнаружить невозможно.

  1. Для передачи сообщений используется код:

A
В данном случае N0=8, N=4. Для данного кода кодовое расстояние dmin=2. Любая одиночная ошибка переводит разрешенное кодовое слово в запрещенное, что позволяет обнаружить наличие ошибок.


000

B

011

C

101

D

110

Действие ошибок большей кратности на данный код выражается в следующем:

  • Код не обнаруживает двойные ошибки, любая двойная ошибка переводит одно разрешенное кодовое слово в другое.

  • Код обнаруживает тройную ошибку e=(111), так как она всегда приводит к появлению запрещенного слова.

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

^ Способность кода обнаруживать ошибки в общем случае определяется следующим образом:

  • Если кодовые слова отличаются друг от друга не менее чем на dmin>=2 символов, то все ошибки веса t<=dmin-1 будут обнаружены.

  • Ошибки веса равного или больше dmin обнаруживаются частично, то есть одни ошибки обнаруживаются, а другие – нет.



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

  1. Построим код, который может исправить одиночную ошибку t=1. Чтобы код мог исправлять одиночные ошибки, то есть определять какое кодовое слово было передано в действительности, разрешенные слова должны отличаться по крайней мере в трех символах d>=3, dmin=3.

A

00000

B

01101

C

10110

D

11011



В этом случае одиночная ошибка переведет переданное слово в одно из запрещенных и, следовательно, будет обнаружена. Полученное запрещенное слово отличается от переданного только одним символом, а от остальных разрешенных слов не менее, чем в двух символах. То есть принятое слово ближе к переданному и менее похоже на остальные разрешенные слова. Это позволяет нам выбрать среди разрешенных слов действительно переданное, а значит исправить ошибку.

Пусть передавалось слово ^ 00000. Было принято слово 01000. Оно является запрещенным, значит ошибка обнаружена. Чтобы определить, какое из слов было передано, приемник сравнивает принятое слово со всеми разрешенными. Из четырех разрешенных слов ближе всего к принятому 00000. Ошибка исправлена.

^ Способность кода исправлять ошибки в общем случае определяется следующим образом:

  • Если код имеет кодовое расстояние dmin>=3, и используется декодирование с исправлением ошибок по ближайшему разрешенному слову, то все ошибки веса tmin/2 исправляются.

  • Ошибки большего веса могут исправляться частично.

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

dmin>=tобн+1

dmin>=2tиспр+1

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

r>=log2(n+1), где

r – число добавочных проверочных символов кода.

N0=2n, n=k+r, N=2k , где

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


Применение помехоустойчивого кодирования позволяет уменьшить вероятность ошибок в сообщении, но выигрыш в помехоустойчивости не приобретается даром. Чтобы воспользоваться корректирующим кодом, необходимо увеличить длину кодовых слов. При неизменной длине единичных элементов сигнала для передачи сообщения теперь потребуется большее время. Если же число сообщений, передаваемых в единицу времени, должно остаться неизменным, то придется сокращать длительность единичных элементов сигнала  . Это вызывает необходимость расширения полосы частот передаваемого сигнала. Чем меньше длительность  , тем больше эффективная полоса частот сигнала. Следовательно, потребуется увеличить полосу частот, отводимую одному каналу системы передачи.


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


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




БЛОЧНЫЕ

НЕПРЕРЫВНЫЕ

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

РАЗДЕЛИМЫЕ

ЛИНЕЙНЫЕ

НЕЛИНЕЙНЫЕ

ИТЕРАТИВНЫЕ

ЦИКЛИЧЕСКИЕ

ХЭММИНГА





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





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




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

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

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

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

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

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

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


^ ЛИНЕЙНЫЕ КОДЫ

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

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

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

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

U=(u1, u2,…….uk)

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

V=(v1, v2,……….vn)

К
одовое слово 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 (матрица проверочных элементов).

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

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

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

Vi=Ui при 1<=i<=k

и

Vi=U1*1,i  U2*2,i  ….  Uk*k,i при k+1<=i<=n


Пример

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

Запишем в виде формул процедуру нахождения символов кодового слова, если задана некоторая информационная последовательность U=(u1,u2,u3). Кодовое слово будет содержать 5 символов V=(v1,v2,v3,v4,v5).




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

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


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

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

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

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

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

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

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

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

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

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


Задача 1

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

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

  1. 1000

  2. 100011

  3. 10101

  4. 11011

  5. 00000

Задача 2

К


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


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

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

Эти уравнения можно решить при помощи проверочной матрицы Н. В случае правильного приема 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 – комбинация или вектор ошибки. ^ Вид синдрома зависит от вида вектора ошибки. Один и тот же синдром соответствует 2k векторам ошибок. Некоторый вектор ошибки e' имеет тот же синдром, что и вектор e, если

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

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

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

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

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

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

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

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

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

Задача

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

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

Y1=01111 +

Y2=111000

Y3=11011

Y4=1011

Y5=10110 +

Задача

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

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

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


^ Код Хэмминга

Код Хэмминга предназначен для исправления одиночных ошибок и имеет кодовое расстояние dmin=3. Значения n и k кодов Хэмминга связаны соотношением 2n-k-1=n . Строки проверочной матрицы Н представляют собой различные ненулевые последовательности длины (n-k). Изначально правила формирования проверочных элементов выбирались (50-е годы) так, чтобы результат контрольных сумм при приеме указывал порядковый номер искаженного элемента.

Пусть ai – информационные символы, bi – проверочные символы. Если проверочные символы разместить в кодовой комбинации на позициях, номера которых являются степенью двойки (1, 2, 4, 8 и т.д.), то получаемый синдром в двоичном виде указывает на номер искаженного элемента. Рассмотрим это на примере кода (7,4).

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

b1 b2 a3 b4 a5 a6 a7

Р
ешим эту систему уравнений относительно b1, b2 и b4.

Т
огда элементы синдрома S=(s2,s1,s0) равны

Н
апример, если ошибка произошла в символе a3 , синдром будет иметь следующий вид S=(011), что означает десятичное число 3.


^ ИТЕРАТИВНЫЕ КОДЫ

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

Информационные символы

Проверочные символы по строкам

Проверочные символы по столбцам

Проверка проверок

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

Рассмотрим итеративный код с проверкой на четность по каждой строке и каждому столбцу. Кодовые комбинации информационных символов представлены в коде ASCII.

1001010

0111010

1110001

1000111

0011001

1

0

0

0

1

1011111

0



Код с проверкой на четность имеет кодовое расстояние dmin=2 , соответственно для итеративного кода dmin=4 . Полученный код исправляет одиночные ошибки и обнаруживает все ошибки нечетного веса. Ошибки четного веса в пределах одной строки обнаруживаются при помощи проверок по столбцам. Четное число ошибок в пределах одного столбца обнаруживается при помощи проверок по строкам. Не обнаруживается любой набор из 4-х ошибок, образующих прямоугольник.


^ Понятие о сверточных кодах

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

^ Сверточные коды являются непрерывными, то есть относятся к классу древовидных кодов. Проверочные символы такого кода образуются путем суммирования по модулю 2 каждого информационного символа с некоторым набором предыдущих символов.

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


Вх

Ui

1

2

3

i

N

РС








1

2

j

m

1

m

M




Вых

Vi





При поступлении на вход кодера каждого информационного символа Ui мультиплексор М последовательно считывает за один такт сигналы с выходов всех сумматоров по модулю 2, формируя на выходе m символов Vi. Таким образом, при скорости входной последовательности Ввх бит/с скорость выходной последовательности составляет Ввых=mВвх бит/с.

^ Для задания схемы кодера сверточного кода пользуются двоичными коэффициентами gij:

  • Если gij =1, значит i-я ячейка регистра сдвига РС имеет связь с j-м сумматором.

  • Если gij =0, значит i-я ячейка регистра сдвига РС не имеет связи с j-м сумматором.

Совокупность связей i-й ячейки РС с сумматорами представляют в виде двоичного вектора Gi=(gi1, gi2, ….,gim), 1<=i<=N.

Второй способ представления связей между ячейками регистра сдвига и сумматорами, который часто используется в научно-технической литературе, заключается в следующем: каждый сумматор записывается в виде порождающего (образующего, формирующего) полинома gj(D)=1+D+D2+D3+…Здесь используется терминология циклических кодов. Степени полинома соответствуют ячейкам регистра сдвига (слева направо), с которыми j-й сумматор имеет связь. Например, в радиоканалах подвижной связи стандарта GSM (Глобальная система подвижной связи) используются сверточные кодеры с N=5 и порождающими полиномами g1=1+D2+D3+D4 и g2=1+D+D4.

Сверточный код может быть систематическим или несистематическим. Для систематического кода один из полиномов gj должен быть равен 1

gj=1.

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

Каждый информационный символ находится в регистре сдвига в течение ^ N тактов и влияет на N*m передаваемых символов Vi. Величина N называется длиной кодового ограничения сверточного кода. В общем случае число символов на выходе сверточного кодера, соответствующее передаче информационной последовательности длиной L символов составляет (L+N)*m. Обычно L>>N.

Сверточный код характеризуется скоростью R=k/n, где k – число входов сверточного кодера, n – число выходов, то есть число сумматоров. На практике чаще всего используются коды со скоростью R=1/2.

^ Пример сверточного кодера

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

G1=(101)

G2=(010)

G3=(011)

По условию N=3, m=3.

1

2

3

N

m

Вх

Вых








1

2

3









Рассмотрим работу кодера. Пусть на вход поступает информационная последовательность U=(101). Каждый такт работы схемы делится на две части: t' – запись нового состояния, t'' – считывание состояния.

№ такта

Символ в ячейке РС

Символ на выходе сумматора

Примечание

1

2

3

1

2

3

1

1

0

0

1

0

1

Ввод в РС

101

2

0

1

0

0

1

0

3

1

0

1

1

1

0

4

0

1

0

0

1

0

На вход поступают нули

5

0

0

1

0

1

1

6

0

0

0

0

0

0



После поступления на вход кодера последнего информационного символа последовательности L на вход поступают N (в нашем случае N=3) нулей. При этом в канал считываются еще 3 группы символов, а регистр возвращается в исходное состояние. В результате сверточного кодирования информационная последовательность 101 превратилась в кодовую комбинацию из 18 символов: 101 010 110 010 011 000. Рассмотренный сверточный код имеет скорость R=1/3 и является систематическим, то есть разделимым.

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


^ Алгоритм декодирования Витерби.

Состояние кодера сверточного кода можно представлять в виде решетчатой структуры. Рассмотрим решетку для сверточного кода с кодовым ограничением 3 и скоростью 1/2.



00

01

10

11

00

01

10

11


01

Ч
0

1

2

3

4

00

00

00

00

11

11

11

11

01

01

10

10

10

10

10

00

00

11

11

01

01
исло вершин на каждом уровне решетчатой диаграммы, начиная со второго (на рисунке показаны уровни 0 – 4) равно 2N-1, где N – длина кодового ограничения, то есть число ячеек в регистре сдвига. Начиная с третьего уровня структура диаграммы повторяется.

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

^ 1011

дает выходную последовательность

11 01 00 10.

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

Предположим передавалась нулевая последовательность. Принятая последовательность имеет вид 10 00 10 00 00….В качестве метрики (оценки расстояния между принятой последовательностью и путем, выбранным по решетчатой диаграмме) служит расстояние Хемминга.

На уровне 2

Принята последовательность 10 00.

На втором уровне решетки имеют место кодовые слова

00 00 t=1

00 11 t=3

11 01 t=2

11 10 t=2

На уровне 3

Принята последовательность 10 00 10.

Каждый из путей с уровня 2 раздваивается. Общее число путей стало равно 8. Сравним метрики для пар путей, ведущих в каждую вершину уровня 3, и в каждой паре сохраним только лучший путь с минимальной метрикой.

00 00 00 t=2

00 00 11 t=2

11 10 10 t=2

00 11 10 t=3

На уровне 4

Принята последовательность 10 00 10 00.

Каждый из путей с уровня 3 раздваивается. Снова сравниваем метрики для пар путей, ведущих в каждую вершину уровня 4, и сохраняем пути с лучшей метрикой.

00 00 00 00  t=2

11 10 10 00  t=2

00 00 11 01  t=3

00 00 11 10  t=3

Оставшиеся пути называются выжившими. Процесс повторяется. В течение некоторого времени выживающие пути отличаются друг от друга. Но на некоторой глубине происходит слияние путей. Для данного примера – это уровень 10. Выжившие пути сливаются на протяжении 8 ребер. Они все выходят из одной вершины, соответствующей передаче символа 0.


П


t=2


t=4


t=5


t=5
олучается следующая решетка








Декодер принимает решение о декодировании информационного символа 0. На практике в декодере устанавливается фиксированная глубина декодирования. Каждый раз при обработке нового ребра решетки декодер выдает самый старый символ одного из выживших путей.


^ ЦИКЛИЧЕСКИЕ КОДЫ

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

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

^ Представление кодовых слов степенными полиномами.

К
одовые слова циклического кода ставят в соответствие степенным полиномам по следующему правилу: двоичной последовательности V длины n

с
оответствует полином (n-1)-й степени

Здесь х – формальная переменная.

Циклический сдвиг кодового слова на i разрядов влево соответствует умножению полинома V(x) на xi по модулю (xn+1).

Пример.

Пусть n=7. Задано кодовое слово 1001101  x6+x3+x2+1. Сдвиг кодового слова на 1 разряд влево дает другое кодовое слово 0011011  х43+х+1.

V(x)*xi mod (xn+1)=(x6+x3+x2+1)*x mod (x7+1)=(x7+x4+x3+x) mod (x7+1)= =x4+x3+x+1

A=BmodC (А равно остатку от деления В на С)

Циклический сдвиг кодового слова на i разрядов вправо соответствует умножению полинома V(x) на x-i или хn-i по модулю (xn+1).

V(x)*x-i mod (xn+1)= V(x)*xn-i mod (xn+1)

^ Порождающий полином циклического кода

Множество кодовых слов циклического кода можно указать, задав любое ненулевое кодовое слово. Обычно для задания циклического кода указывают полином наименьшей степени g(x) , который полностью определяет код и называется порождающим. Степень порождающего полинома равна (n-k) , а свободный член V0 всегда равен 1.

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

  1. В качестве первой строки матрицы записывают g(x), дополнив комбинацию нулями слева для получения кодового слова длиной n символов.

  2. Вторая строка – x*g(x) (циклический сдвиг первой строки на одну позицию влево).

  3. Третья строка – x2*g(x) (циклический сдвиг первой строки на две позиции влево).

……………………………………………………………………………………..

  1. К-я строка – xk-1*g(x) (циклический сдвиг первой строки на (k-1) позицию влево).

Пример.

З
адан код (7,4) с порождающим полиномом g(x)=x3+x+1. Требуется записать его порождающую матрицу.

^ Полиномы кодовых слов циклического кода делятся без остатка на свой порождающий полином g(x).

Выбор g(x) для построения циклического кода длины n.

Любой полином, который является делителем полинома (xn+1) можно использовать в качестве порождающего. С ростом n число возможных циклических кодов растет. На практике при построении циклических кодов пользуются таблицами разложения полиномов (xn+1) на неприводимые полиномы. Любой неприводимый полином, входящий в разложение, или произведение нескольких неприводимых полиномов можно выбрать в качестве порождающего полинома, который дает соответствующий циклический код.

Пример.

Требуется определить, какие циклические коды можно построить при длине кодового слова n=7.

x7+1=(x+1)(x3+x2+1)(x3+x+1)

Можно построить следующие ЦК:

  1. (7,6) с g(x)=x+1

  2. (7,1) с g(x)= (x3+x2+1)(x3+x+1)=x6+x4+x3+x5+x3+x2+x3+x+1=

=x6+x5+x4+x3+x2+x+1

  1. (7,4) c g(x)= x3+x2+1

  2. (7,4) c g(x)= x3+x+1

  3. (7,3) c g(x)= (x+1)(x3+x2+1)=x4+x3+x+x3+x2+1=x4+x2+x+1

  4. (7,3) c g(x)= (x+1)(x3+x+1)=x4+x2+x+x3+x+1=x4+ x3+x2+1

Процедура кодирования циклическим кодом

Процедура кодирования записывается следующим образом:

V(x)=U(x)*xn-k+R(x)

R(x)= U(x)*xn-k mod g(x)

В этом случае первые k разрядов кодового слова являются информационными, а последние r=n-k - проверочными.

Пример

Закодировать информационную последовательность U=0110 циклическим кодом (7,4) с порождающим полиномом g(x)= x3+x+1.

U(x)= x2+x, r=n-k=3, U(x)*x3= x5+x4

R
(x)=( x5+x4) mod (x3+x+1)

R(x)=1

V=0110001  V(x)= x5+x4+1

Сложение коэффициентов при одинаковых степенях осуществляется по модулю 2.

Деление можно выполнять в двоичном виде.

U(x)*x3= x5+x4 0110000

g(x) 1011

R
=001V=0110001

Число проверочных символов равно степени порождающего полинома.

Задача

Разделимый циклический код (7,4) задан порождающим полиномом

g(x)= x3+x2+1.

Соответствуют ли кодовые слова информационным последовательностям?

  1. U1=1101 V1=1101000

  2. U2=0001 V2=0001110

  3. U3=1011 V3=1011100

Процедура декодирования циклического кода

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

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

Если принятая комбинация Y(x) делится без остатка на g(x), то считается, что ошибок нет или произошла не обнаруживаемая кодом ошибка. В случае обнаруженной ошибки имеет место ненулевой остаток от деления, который называется синдромом.

S(x)=Y(x) mod g(x)=e(x) mod g(x)

Здесь e(x) – полином ошибки.

Д
еление на порождающий полином можно заменить умножением на проверочный полином h(x) по модулю (xn+1). Результат в случае отсутствия ошибок должен быть равен нулю.

[Y(x)*h(x)] mod (xn+1)=0


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

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

Пусть ошибке вида e0 соответствует синдром S0. Назовем их типовыми.

S0(x)=e0(x) mod g(x)

Если вектор ошибки e' получается из e0 путем i циклических сдвигов, то есть

e'(x)=e0 (x)*xi mod (xn+1),

то синдром ошибки e' будет равен

S'(x)=S0(x)*xi mod g(x),

а S0(x)= S'(x)* x-i mod g(x)

Пример

Пусть для передачи сообщений используется циклический код (7,4) с порождающим полиномом g(x)= x3+x2+1. Декодер работает в режиме исправления одиночных ошибок.

При использовании ДСК без памяти таблица декодирования имеет вид

Вектор ошибки ei

Синдром Si

0000001

001

0000010

…………..

010

…….

1000000

110

В качестве типовых обычно выбирают e0=0000001 и S0=001.

Предположим при декодировании получен синдром S'=100. Требуется найти имеющий место вектор ошибки и исправить кодовое слово.

S0(x)=S'(x)*x-i mod g(x)

Если i=1, S1= x2* x-1 mod g(x)=x, не совпадает с типовым синдромом.

Если i=2, S2=x2*x-2 mod g(x)=1, совпадает с типовым синдромом.

Искомый вектор ошибки получается циклической перестановкой типового вектора e0 на i=2 разряда влево.

e'=0000100


^ КОДИРУЮЩИЕ И ДЕКОДИРУЮЩИЕ УСТРОЙСТВА ЦИКЛИЧЕСКИХ КОДОВ

Основой кодера циклического кода является регистр сдвига (РС) с логическими обратными связями и сумматорами по модулю 2. Число ячеек памяти регистра равно r=n-k, число сумматоров по модулю 2 на единицу меньше числа ненулевых членов g(x). Место включения сумматоров определяется структурой (ненулевыми коэффициентами) порождающего полинома g(x).

^ Схема кодирующего устройства в общем виде

Нижеприведенная схема делит входную последовательность на полином

g
Вх
(x)=grxr+gr-1xr-1+….+g1x+g0


1

Вых

0

1

2

r-1



g0

g1

g2

gr-1





  1. 2

Ключ

Например, для кода с порождающим полиномом g(x)=x3+x2+1 получаем g0=1, g1=0, g2=1. Получаем схему:


1

Вх



0

1

2

Вых



g0

g2





  1. 2

Ключ

В исходном состоянии Ключ находится в положении 1. Символы информационной последовательности, начиная со старшего разряда, поступают на вход схемы деления через входной сумматор и ключ (1) и одновременно через схему ИЛИ (1) на выход кодера. Через k тактов в регистре сдвига образуются проверочные символы, ключ переводится в положение (2) и проверочные символы поступают через схему ИЛИ на выход. Таким образом через n тактов на выходе формируется кодовое слово циклического кода.

Рассмотрим, как меняется состояние схемы на каждом такте работы кодера.

№ такта


Инф.символ на входе

Символ в ячейке РС

Положение ключа

Символ на выходе

0

1

2

1

1

1

0

1

1

1

2

0

1

1

1

1

0

3

0

1

1

0

1

0

4

0

0

1

1

1

0

5

0

0

0

1

2

1

6

0

0

0

0

2

1

7

0

0

0

0

2

0

Используется 2-тактная работа схемы:

T
T' ' – считывание состояния

T'' – запись

Проверим, правильно ли сформированы проверочные символы:

10000000 |1101

1101

1010

1101

1110

1101

110 – проверочные символы найдены верно


Декодер циклического кода

Декодер циклического кода должен вычислять синдром и состоит из запоминающего регистра с числом ячеек памяти равным n и схемы деления на g(x). Кроме того, декодер содержит схемы дешифратора ошибки и устройства исправления либо стирания принятой кодовой комбинации.

Рассмотрим схему декодера циклического кода (7,4) с порождающим полиномом g(x)=x3+x2+1.

Запоминающий регистр

Вх

0

1

2

3

4

5

6

0

1

2


Вых

УИс

УСт

Схема деления на g(x)










Дешифратор ошибки

Рассмотрим два случая:

  1. Поступающее на вход декодера кодовое слово не содержит ошибок.

На вход поступает последовательность 1000110.

№ такта

Символ на входе

Символ в ячейке схемы деления

0

1

2

1

1

1

0

0

2

0

0

1

0

3

0

0

0

1

4

0

1

0

1

5

1

0

1

1

6

1

0

0

0

7

0

0

0

0

S=(000), ошибки в принятой последовательности не обнаружены. Деление закончено. Кодовое слово последовательно поступает из запоминающего регистра на выход декодера.



  1. Поступающая последовательность содержит ошибку

e(x)=x3  0001000, следовательно на вход поступает комбинация 1001110.



№ такта

Символ на входе

Символ в ячейке схемы деления

0

1

2

1

1

1

0

0

2

0

0

1

0

3

0

0

0

1

4

1

0

0

1

5

1

0

0

1

6

1

0

0

1

7

0

1

0

1

8

0

1

1

1

9

0

1

1

0

10

0

0

1

1

11

0

1

0

0

На 7-м такте в ячейках схемы деления сформирован синдром S', не совпадающий с S0 и не равный нулю.

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

Если декодер работает с исправлением ошибок, процесс деления продолжается до тех пор, пока в ячейках схемы деления не образуется синдром S0=001. В данном случае деление продолжается в течение 8 – 11 тактов. Начиная с 8-го такта на выходе декодера появляются символы кодового слова, начиная со старшего разряда (коэффициент при х6). На 11 – м такте в ячейках схемы деления образуется типовой синдром S0. Дешифратор ошибки формирует сигнал, изменяющий на выходе текущий символ кодового слова (коэффициент при х3). Деление закончено. Ошибка исправлена.




Скачать 384,81 Kb.
оставить комментарий
Дата07.08.2012
Размер384,81 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх