Смекни!
smekni.com

Передача информации по каналу с решающей обратной связью (стр. 7 из 11)


Найдём дополнительную матрицу:

100000000|100111

100111 |—————————————————————

——————————

00111000111: 1-й остаток

————————

01110001110: 2-й остаток

————————

11100011100: 3-й остаток

100111

———————

11111011111: 4-й остаток

100111

————————

11001011001: 5-й остаток

100111

————————

10101010101: 6-й остаток

100111

————————

0110101101: 7-й остаток

————————

11010011010:8-й остаток

100111

————————

10011010011: 9-й остаток

100111

————————

000001


Итак, дополнительная матрица имеет вид:

m5 m4 m3 m2 m1
0 0 1 1 1
0 1 1 1 0
1 1 1 0 0
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
0 1 1 0 1
1 1 0 1 0
1 0 0 1 1

Составим образующую матрицу:

k9 k8 k7 k6 k5 k4 k3 k2 k1 m5 m4 m3 m2 m1
0 0 0 0 0 0 0 0 1 0 0 1 1 1
0 0 0 0 0 0 0 1 0 0 1 1 1 0
0 0 0 0 0 0 1 0 0 1 1 1 0 0
0 0 0 0 0 1 0 0 0 1 1 1 1 1
0 0 0 0 1 0 0 0 0 1 1 0 0 1
0 0 0 1 0 0 0 0 0 1 0 1 0 1
0 0 1 0 0 0 0 0 0 0 1 1 0 1
0 1 0 0 0 0 0 0 0 1 1 0 1 0
1 0 0 0 0 0 0 0 0 1 0 0 1 1

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

1.5 Расчет достоверности передаваемых сообщений

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

1. Для симметричного канала с независимыми ошибками.

Согласно ТЗ, P10=P01 =0,5.

Для одиночных ошибок:

Для двух ошибок:

Общая вероятность:

Это означает, что на 1000 переданных символов 7 будут с ошибкой. Тогда для 1000 сиволов достоверность будет 993/1000=0,993 или 99,3%.

2. Для несимметричного канала с независимыми ошибками.

Согласно ТЗ, P10=0,3

P01 =0,7.

Пусть сообщение будет следующим G=11001010101011, а искаженное G1=01101010101011.

Общая вероятность:

Это означает, что на 1000 переданных символов 2 будут с ошибкой. Тогда для 1000 сиволов достоверность будет 998/1000=0,998 или 99,8%.

1.6 Выводы

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


2. Техническая реализация кодера, декодераи решателей

2.1 Модульная структура кодера и его работа

Основу кодирующих устройств двоичных циклических кодов составляют регистры сдвига с обратными связями, позволяющие осуществлять как умножение, так и деление многочленов с приведением коэффициентов по модулю 2. Такие регистры также называют многотактными линейными переключательными схемами и линейными кодовыми фильтрами Хаффмена. Они состоят из ячеек памяти, сумматоров по модулю 2 и устройств умножения на коэффициенты многочленов множителя или делителя. В случае двоичных кодов для умножения на коэффициент, равный 1, требуется только наличие связи в схеме. Если коэффициент равен 0, то связь отсутствует. Сдвиг информации в регистре осуществляется импульсами, поступающими с генератора продвигающих импульсов. На вход устройств поступают только коэффициенты многочленов, причем начиная с коэффициента при переменной в старшей степени.

Как указывалось выше, образование циклического кода состоит из двух операций: умножения комбинации обычного двоичного кода G(X) на одночлен Xm и последующего деления этого произведения на выбранный образующий многочлен P(X). Полученные в остатке от деления контрольные символы приписываются к кодируемой комбинации. Таким образом, кодирующее устройство должно совмещать функции умножения и деления.

Рассмотрим методику построения кодирующего устройства. Требуется составить схему кодирующего устройства для многочлена:

P(X)=X5+X2+X+1.

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

Рис.2.1. Схематичное изображение кодирующего устройства

Схема, изображенная на рис. 2.1, работает следующим образом. В исходном состоянии ключ К1 находится в положении 1, а ключ К2 замкнут. Все подлежащие кодированию информационные символы, начиная со старшего разряда, поступают одновременно на выход и через сумматор на входе в схему кодирования. После того как пройдет последний символ k, ключ К1 переключится в положение 2, а ключ К2 размыкается. После этого регистр делает m шагов, равных числу ячеек, т.е. пять шагов. И весь остаток поступает на выход. Этот остаток представляет собой контрольные символы, следующие за информационными символами.

Рассмотрим подробнее процесс кодирования комбинации

Процесс кодирования комбинации G(X)= 000100000 с помощью кодера на рисунке 2.1, а показан в таблице 2.1.

В тактах 1-3 на вход поступают нули, поэтому в регистре ничего не меняется. Только в такте 4 единица кодируемого записывается в ячейки X0, X1, X2 и поступает на выход. В такте 5 на вход поступает нуль, поэтому в X0 поступает 0, и на выходе тоже 0. Из ячеек X0, X1, X2 единицы перемещаются в ячейки X1, X2, X3.

Аналогично и в такте 6, три единицы перемещаются далее вправо. На такте 7 единица из ячейки X4 поступает на сумматор по модулю 2 и складывается там с 0, поступающим с входа. Тогда, в результате сложения 1 и 0 по модулю 2 получается 1, которая поступает на остальные суммирующие элементы по модулю 2. В итоге во всех ячейках будут записаны 1. В тактах 7, 8, 9 просходит аналогично такту 6.

Таблица 2.1. Образование циклического кода

Номер такта Вход Состояние ячеек регистра Выход
X0 X1 X2 X3 X4
123456789 000100000 0000100111 0000110100 0000111101 0000011110 0000001111 000100000
1011121314 00000 10000 01000 10100 01010 10101

После такта 9 остаток R(X) оказывается записанным в ячейках регистра. После переключения ключа K1 в положение 2 и выключения ключа K2 этот остаток в последующие четыре такта переписывается на выход вслед за информационными символами.

2.2 Модульная структура декодера и его работа

Декодирование циклического-кода с обнаружением и исправлением нескольких ошибок. Метод такого декодирования был изложен в теоретическом введении. Рассмотрим теперь схемную реализацию декодирования комбинации 10000000010011, искаженную одним символом и принявшей вид 10010000010011. Декодер (рис.2.2) состоит из делителя, выполненного для деления на многочлен P(X)=X5+X2+X+1, и запоминающего устройства, представляющего собой регистр с сумматором символов k. Комбинация поступает одновременно на делитель и запоминающее устройство начиная со старшего разряда. Искаженный символ в комбинации отмечен почеркиванием. Вначале ключ K1 замкнут, а ключ К2 разомкнут. В таблице 2.2 показан процесс деления начиная с такта 6, так как в первые пять тактов происходит заполнение делителя и обратная связь еще не проявляется.

Рис. 2.2. Сруктурная схема декодирования циклического кода с исправлением одной ошибки.

В такте 6 единица с Х4 поступает на сумматоры по модулю 2, и в X0 записывается единица, нуль, находившийся в X0, сложившийся с единицей даст 1 и она запишется в X1 , единица из X1 сложившись с 1 даст нуль и этот нуль запишется в X2, нуль из X2 перейдёт в X3, а единица из X3 в X4. Далее аналогично.

Таблица 2.2. Работа делителя

Номер такта Делимое Состояние ячеек делителя Весостатка
X0 X1 X2 X3 X4
6789101112131415161718 000010011 1000010011011 1100111100110 0110101011000 0011010101100 0001101010110 33331

В такте 14 синдром (остаток от деления) оказывается записанным в ячейках регистра (10101). Однако его вес W=3 больше числа исправляемых ошибок s, поэтому делитель делает еще один шаг (такт 15), в процессе которого снова осуществляется деление на многочлен Р(Х). Синдром 10110 опять имеет вес W=3. Только после 18 такта W=1=s. В этот момент ключ К1 размыкается, а ключ К2 замыкается и синдром с делителя начинает поступать на сумматор запоминающего устройства, у которого ключ К3 замкнут, а ключ К4 разомкнут.