Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Учебное пособие Основы передачи дискретных сообщений - файл 1.doc


Учебное пособие Основы передачи дискретных сообщений
скачать (4581 kb.)

Доступные файлы (1):

1.doc4581kb.15.12.2011 14:12скачать

1.doc

1   2   3   4   5   6   7


^ Код Хемминга.

Код Хэмминга является разновидностью линейных кодов и позволяет не только обнаруживать, но и исправлять ошибки. В коде Хемминга вводится понятие кодового расстояния– это степень различия кодовых комбинаций . Кодовое расстояние для двух любых кодовых комбинаций определяется числом несовпадающих в них разрядов. Наименьшее кодовое расстояние называется минимальным кодовым расстоянием ( расстояние Хемминга ).

К кодам Хемминга обычно относятся коды с =3, исправляющие все одиночные ошибки и коды с =4, исправляющие все одиночные и обнаруживающие все двойные ошибки. Для исправления всех одиночных ошибок число синдромов должно быть n+1 ( n – число разрядов ). Из них n синдромов используются для указания местоположения ошибки, а один – нулевой, соответствует их отсутствию. Следовательно, . n=m+k, где m –информационные разряды, к –проверочные.

Для проверочных разрядов выбираются комбинации, где присутствует одна «1», остальные будут информационными.




Сгруппируем в первую сумму все элементы, номера которых имеют значение «1» в 1-м младшем разряде двоичного числа. Во вторую сумму сгруппируем элементы, номера которых имеют значение «1» во втором разряде двоичного числа и т.д. для третьей и четвертой сумм.









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

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



Порядок кодирования кодом Хемминга в устройстве защиты от ошибок передатчика:

1. от источника принимается 5-ти элементная кодовая комбинация и ее разряды записываются в отведенных для них местах 3,5,6,7 и 9.

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

3. Полученные проверочные элементы размещаются на отведенных для них местах 1,2,4 и 8 в полной кодовой комбинации.

4. Сформированная таким образом кодовая комбинация передается в канал.
Рассмотрим пример: Источник выдает информационные элементы










Тогда полная кодовая комбинация, которая будет передаваться в канал, имеет вид:


Порядок декодирования на приеме в устройстве защиты от ошибок.

1. Подсчитываем 4 суммы в каждую из которых входят информационные разряды и по одному проверочному.

2. Производится анализ полученных сумм, при этом возможны три случая:

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

б) проверочное число отличается от значения 0000, причем по его значению можно определить номер ошибочного разряда;

в) проверочное число отличается от значения 0000, но определить место ошибки невозможно;

3. В зависимости от результатов анализа:

а) информация выдается потребителю;

б) ошибки исправляются и информация выдается потребителю;

в) принятая комбинация стирается и в устройстве защиты от ошибок вырабатывается сигнал «ошибка».

Принята комбинация:










Все «0», значит комбинация принята верно.

Допустим что произошло искажение в третьем элементе и вместо 1 принят 0. Тогда принятая комбинация имеет вид:











В данном случае синдром равен 0011, что соответствует ошибке в 3 элементе кодовой комбинации. Для устранения данной ошибки необходимо изменить находящийся в этом элементе символ на обратный.




Рисунок 3.9 - Схема кодера.



Рисунок 3.10 - Схема декодера.
Декодер путем сложения по модулю 2 от схемы «И» и от информационного разряда позволяет исправить ошибку, возникшую в процессе передачи.

Код Хемминга имеет существенный  недостаток:  при  обнаружении любого числа ошибок он исправляет лишь одиночные  ошибки. Избыточность  семиэлементного кода Хемминга равна 0,43. При увеличении значности кодовых комбинаций увеличивается число проверок,  но уменьшается избыточность кода.

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

^ Циклическое кодирование.

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

1. Любая из разрешенных кодовых комбинаций циклического кода делится по модулю два без остатка на некоторое, так называемое «образующее двоичное число», определяющее помехоустойчивые свойства кода, т.е. расстояние d;

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

Например: 01011 и 10110 – две разрешенные кодовые комбинации некоторого циклического кода с образующим числом 1011 (d=3). Поэтому они делятся по модулю два без остатка на образующее число:

1011 1011 10110 1011

0000 01 1011 10

1011 0000

1011 0000

000 000

При этом d=4 > d=3.

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



01011 => 10110

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

Структурная схема СПДС, содержит кодер и декодер циклического кода. Структура разрешенных кодовых комбинаций циклического кода состоит из двух частей. В начале комбинации располагается n-проверочных разрядов, структура которых определяется кодерами циклического кода из условия обеспечения делимости без остатка формируемой разрешенной кодовой комбинации на образующее число.

Идея построения циклического кода (n,k) сводится к тому, что информационную часть кодовой комбинации G(x) нужно преобразовать в комбинацию F(x), которая без остатка делится на порождающий полином Р(х) степени r=n-k. Рассмотрим последовательность операций построения циклического кода:

1. Представляем информационную часть кодовой комбинации в виде полинома G(x). Например информационная часть 110101. Тогда .

2. Умножаем G(x) на одночлен ( старшую степень порождающего полинома Р(х) ) и получаем .

Пусть у нас порождающий полином 1011, тогда .

3. Делим на порождающий полином Р(х), при этом получаем остаток от деления R(x).



Добавим полученный остаток R (x) к комбинации и получим комбинацию , которая будет передана в линию. Данная комбинация F(x) делится без остатка на образующий полином и представляет собой разрешенную кодовую комбинацию циклического (n,k) кода. На приеме производится деление полученной кодовой комбинации на образующий полином. Если ошибок нет, то деление пройдет без остатка. Если при делении получен остаток, то комбинация принята с ошибками.

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

^ Построение кодеров, декодеров.

Пример:

Кодер строится на основе полинома P(x).

=> 1011 – веса

При построении устройства число ячеек регистров сдвига берется по высшей степени образующего полинома => 3 регистра сдвига; число регистров задержки берется также по высшей степени образующего полинома; число сумматоров по модулю два берется по весовой части образующего полинома минус единица => 3-1=2m.



РЗ


РС
^ Состояния регистров сдвига (1,2,3 – регистры; m – сумматоры)

На вход подается 110101000



Декодер – правила построения такие же, как у кодера, но количество регистров задержки определяется по высшей степени информационной комбинации плюс 1  5+1=6

РЗ


РС


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

1. Если хотя бы в одной ячейке регистра будет «1», то значит произошла ошибка. Формируется сигнал «1» и информация из регистров сдвигов будет удаляться.

2. Если во всех ячейках регистров сдвига будут «0», то формируется сигнал «0» и информация будет выдана потребителю.

^ Состояния регистров сдвига


Если хотя бы в одной ячейке регистра будет «1», то значит произошла ошибка.

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

^ Выбор образующего полинома.

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

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

=1 если n=7, то

tи.ош – число ошибок, исправляемых циклическим кодом.

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

Таблица 3.1 – Таблица минимальных многочленов


r

Pr(x)

Двоичная запись

2



111

3



1011

1101


В частности, если r=3, tи.ош=1, j=2*1-1=1, образующий полином будет представлять собой единственный минимальный многочлен P(x)= x3+x+1 (первая строка, второй столбец таблицы ). Соответственно образующее число равно 1011.

Синдром циклического кода.

Синдром циклического кода определяется суммой по модулю 2 принятых проверочных элементов и элементов проверочной группы, сформированных из принятых элементов информационной группы. В циклическом коде для определения синдрома следует разделить принятую кодовую комбинацию на кодовую комбинацию порождающего полинома. Если все элементы приняты без ошибок, то остаток от деления R(х) равен нулю. Если есть ошибки, то остаток не будет равен нулю. Следовательно, синдромом циклического кода является многочлен R(x). Обнаружение и исправление ошибок производится только на основе анализа синдрома. В зависимости от остатка определяется элемент в котором произошла ошибка. Для исправления ошибок необходимо чтобы количество ненулевых остатков равнялось количеству элементов n ( при исправлении одной ошибки ) или числу комбинаций из n.
1   2   3   4   5   6   7



Скачать файл (4581 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации