Передача информации по каналу с решающей обратной связью (стр. 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 разомкнут.