Автор работы: Пользователь скрыл имя, 13 Октября 2014 в 18:01, реферат
Цель и суть любого кодирования представление сообщений в форме удобной для их последующей обработки, а также для передачи хранения и выполнения арифметических и логических операций. Сообщения могут быть представлены в форме кодовых слов.
Идея помехоустойчивого кодирования состоит в том ,что кодер вносит избыточную информациию в виде правил кодирования добавляя дополнительные разряды помехоустойчивого кодового слова с последующей проверкой.
Искажение помехой: 1001111111
Декодирование:
1Å1Å1Å 0 Å 1Å 1=1
1Å 1 Å 0 Å 1=1
1Å 1Å 1=1
1Å1Å 1Å0=1
Опознаватель 1111 => вектор ошибки отсутствует
Восстановление не требуется.
На выходе дешифратора сигнал ошибки.
б) 000111 [ Кодер ]0000111101 [ канал связи ] 000010100[дешифратор] ошибка
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0000010101
Декодирование:
0 Å 0 Å 0 Å 0Å 0=0
0 Å 1 Å 0 Å 0=1
0 Å 1 Å 0 =1
0 Å 0 Å 0 Å 0 Å 0=0
Опознаватель 0110 => вектор ошибки отсутствует
Восстановление не требуется.
На выходе дешифратора сигнал ошибки.
Построение неоптимального помехоустойчивого кода.
Исходная информация для построения кода:
Тип исправляемых ошибок –некореллированные
Кратность исправляемых ошибок – S =1 ;
Объем кода (число кодируемых сообщений) - Q =17;
n’-n=2
Число информационных и избыточныхразрядов определяется из соотношений
2k – 1 ≥ Q ;
2n – k – 1 ≥ n ;
n – k ;
где k – число информационных разрядов ;
n - число разрядов помехоустойчивого слова;
(n – k) – число избыточных разрядов;
отсюда k = 5; n =9; n – k = 4;
2.Построение таблицы опознавателей ошибок.
Из таблицы видно, что каждой ошибке соответствует свой опознаватель. В таблице не используются двоичные числа, которые соответствуют номерам поврежденных разрядов,
так как тогда у нас получится код Хэмминга
А11 |
А10 |
A9 |
A8 |
A7 |
A6 |
A5 |
A4 |
A3 |
A2 |
A1 |
Опознаватели |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
000001 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
010100 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
101010 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
000010 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
001001 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
000100 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
011010 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
001000 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
010000 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
100000 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
010001 |
3.Построение проверочных равенств
Проверочное равенство представляет собой одно из преобразованных уравнений алгоритма кодирования . Если при проверке дешифратором уравнений, определяющих данные избыточные разряды, произошло нарушение четности, то опознаватель окажется равным 1.
Разряды опознавателя определяются следующими проверочными равенствами
а1 Ú а5 Ú а11
а3 Ú а4 Ú а7
а2 Ú а6
а3 Ú а5 Ú а7 Ú а8
а2 Ú а7 Ú а9 Ú а11
а3 Ú а10
Запишем проверочные равенства в виде системы уравнений:
а1 Å а5 Å а11
а3 Å а4 Å а7
а2 Å а6
а3 Å а5 Å а7 Å а8
а2 Å а7 Å а9 Å а11
а3 Å а10
4.Построение правила кодирования.
Из системы уравнений приведенной выше составим следующее правило кодирования.
Избыточными разрядами будем считать такие разряды ,которые в проверочных равенствах встречаются по одному разу.
а1 = а5 Å а11
а4 = а3 Å а7
а6 = а2
а8 = а3 Å а5 Å а7
а9 = а2 Å а7 Å а11
а10 = а3
5.Построение кодирующей таблицы.
000001 |
00100100010 |
000010 |
01010001100 |
000011 |
01110101110 |
000100 |
00010010001 |
000101 |
00110110011 |
000110 |
01000011101 |
000111 |
01100111111 |
001000 |
00111001000 |
001001 |
00011101010 |
001010 |
01101000100 |
001011 |
01001100110 |
001100 |
00101011001 |
001101 |
00001111011 |
001110 |
01111010101 |
001111 |
01011110111 |
010000 |
10100000001 |
010001 |
10000100011 |
6.Построение таблицы декодирования.
00100100010 01010001100 01110101110 00010010001 00110110011 01000011101 01100111111 00111001000 00011101010 01101000100 01001100110 00101011001 00001111011 01111010101 01011110111 10100000001 10000100011 |
00000000000 |
00100100011 01010001101 01110101111 00010010000 00110110010 01000011100 01100111110 00111001001 00011101011 01101000101 01001100111 00101011000 00001111010 01111010100 01011110110 10100000000 10000100010 |
00000000001 |
00100100000 01010001110 01110101100 00010010011 00110110001 01000011111 01100111101 00111001010 00011101000 01101000110 01001100100 00101011011 00001111001 01111010111 01011110101 10100000011 10000100001 |
00000000010 |
00100100110 01010001000 01110101010 00010010101 00110110111 01000011001 01100111011 00111001100 00011101110 01101000000 01001100010 00101011101 00001111111 01111010001 01011110011 10100000101 10000100111 |
00000000100 |
00100101010 01010000100 01110100110 00010011001 00110111011 01000010101 01100110111 00111000000 00011100010 01101001100 01001101110 00101010001 00001110011 01111011101 01011111111 10100001001 10000101011 |
00000001000 |
00100110010 01010011100 01110111110 00010000001 00110100011 01000001101 01100101111 00111011000 00011111010 01101010100 01001110110 00101001001 00001101011 01111000101 01011100111 10100010001 10000110011 |
00000010000 |
00100000010 01010101100 01110001110 00010110001 00110010011 01000111101 01100011111 00111101000 00011001010 01101100100 01001000110 00101111001 00001011011 01111110101 01011010111 10100100001 10000000011 |
00000100000
|
00101100010 01011001100 01111101110 00011010001 00111110011 01001011101 01101111111 00110001000 00010101010 01100000100 01000100110 00100011001 00000111011 01110010101 01010110111 10101000001 10001100011 |
00001000000 |
00110100010 01000001100 01100101110 00000010001 00100110011 01010011101 01110111111 00101001000 00001101010 01111000100 01011100110 00111011001 00011111011 01101010101 01001110111 10110000001 10010100011 |
00010000000 |
00000100010 01110001100 01010101110 00110010001 00010110011 01100011101 01000111111 00011001000 00111101010 01001000100 01101100110 00001011001 00101111011 01011010101 01111110111 10000000001 10000100011 |
00100000000 |
01100100010 00010001100 00110101110 01010010001 01110110011 00000011101 00100111111 01111001000 01011101010 00101000100 00001100110 01101011001 01001111011 00111010101 00011110111 11100000001 11000100011 |
01000000000 |
10100100010 11010001100 11110101110 10010010001 10110110011 11000011101 11100111111 10111001000 10011101010 11101000100 11001100110 10101011001 10001111011 11111010101 11011110111 00100000001 00000100011 |
10000000000 |
1. Отсутствие
ошибок в канале связи.
а) 01100 [ КОДЕР ] 00101011001 [КАНАЛ СВЯЗИ] 00101011001 [ ДЕКОДЕР ] 00110
б) 10001 [ КОДЕР ] 10000100011 [КАНАЛ СВЯЗИ] 10000100011 [ ДЕКОДЕР ] 10001
2. Ошибка опознана и исправлена верно.
а) 01001 [ КОДЕР ] 00011101010 [КАНАЛ СВЯЗИ] 00011101110 [ ДЕКОДЕР ] 01001
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0000000100
Декодирование:
0 Å 0 Å 0 =0
1 Å 1 Å 1=1
1 Å 1 =0
1 Å 0 Å 1 Å 1=1
1 Å 1 Å 0 Å 0 =0
0 Å 1 =1
Опознаватель 101010 => вектор ошибки 0000000100
Восстановление
00011101110
Å 00000000100
00011101010
Выделение содержимого информационных разрядов 01001
б) 00101 [ КОДЕР ] 00110110011 [КАНАЛ СВЯЗИ] 00111110011 [ ДЕКОДЕР ] 00101
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 00001000000
Декодирование:
1Å 1 Å 0 =0
0 Å 0 Å 1=1
1 Å 1=0
0 Å 1 Å 1 Å 1=1
1 Å 1 Å 1 Å 0=1
0 Å 0 =0
Опознаватель 011010=> вектор ошибки 00001000000
Восстановление
00111110011
Å 00001000000
00110110011
Выделение содержимого информационных разрядов 00101
3. Ошибка
опознана но исправлена
а)1001[Кодер] 100001110 [ канал связи ] 10000110010[декодер] 1010
Кодирование: находим
в таблице кодирования кодовое
слово соответствующее
Искажение помехой: 00000010001
Декодирование:
0 Å 1 Å 1 =0
0 Å 0 Å 0 =0
1 Å 1 =0
0 Å 0 Å 1 Å 0 =1
0 Å 1Å 0 Å 1 =0
0 Å 0 =0
Опознаватель 001000 => вектор ошибки 00010000000
Восстановление
10000110010
Å 00010000000
10010110010
Выделение содержимого информационных разрядов 10101
б) 00110[кодер] 01000011101[канал связи] 01010010001[ декодер] 00100
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 00010001101
Декодирование:
1Å 1 0 =0
0 Å 0 Å 0=0
0 Å 0=0
1 Å 0 Å 1 Å 0 =0
0 Å 0 Å 0 Å 0 =0
1 Å 0 =1
Опознаватель 100000 => вектор ошибки 01000000000
Восстановление
01010010001
01000000000
00010010001
Выделение содержимого информационных разрядов 00100
4.Ошибка не обнаруживается.
а) 01110 [ Кодер ] 01111010101 [ канал связи ] 01011110111[дешифратор] 01111
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 00100100010
Декодирование:
1Å 1Å 0 =0
0 Å 1Å 1=0
1 Å 1 =0
1 Å 1Å 1 Å 1=0
0 Å 1Å 1Å 0=0
Опознаватель 000000 => вектор ошибки 00000000000
Восстановление не требуется.
Выделение содержимого информационных разрядов 01111
б) 01010 [ Кодер ] 0110100010 [ канал связи ] 00111001000[дешифратор] 01000
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 01010001100
Декодирование:
0 Å 0Å 0 = 0
1 Å 0 Å 1 = 0
0 Å 0 =0
1 Å 0 Å 0 Å 1=0
1 Å 0 Å 1 Å 0 =0
0 Å 0=0
Опознаватель 000000 => вектор ошибки 00000000000
Восстановление не требуется.
Выделение содержимого информационных разрядов 01000
5.Ошибка только обнаруживается
а) 00001 [ Кодер ]00100100010 [ канал связи ] 01000100010[дешифратор] ошибка
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 01100000000
Декодирование:
0 Å 0 Å 0 =0
0 Å 0 Å 0 =0
1 Å 1 =0
0 Å 0 Å 0 Å 0 =0
0 Å 1 Å 0 Å 0 =1
1 Å 0 =1
Опознаватель 110000 => вектор ошибки отсутствует
На выходе дешифратора сигнал ошибки.
б) 00011 [ Кодер ] 01110101110 [ канал связи ] 01110100111[дешифратор] ошибка
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0000001001
Декодирование:
1 Å0Å 0=1
0Å1Å0=1
1Å1=0
1Å1Å0Å0=0
1Å1Å0Å0=0
1Å1=0
Опознаватель 000011 => вектор ошибки отсутствует
На выходе дешифратора ошибка
Построение группового кода для исправления двукратных ошибок.
Исходная информация для построения кода:
Тип исправляемых ошибок – некоррелированные
Кратность исправляемых ошибок – S =2 ;
Объем кода (число кодируемых сообщений) - Q =5;
1.Расчет числа информационных и избыточных разрядов.
Число информационных и избыточных разрядов определяется из соотношений
2k – 1 ≥ Q:
2n-k – 1 ≥ n2 + n /2:
где k – число информационных разрядов ;
n - число разрядов помехоустойчивого слова;
(n – k) – число избыточных разрядов;
отсюда k = 3; n =10; n – k = 7;
2.Построение таблицы опознавателей ошибок.
Из таблицы видно, что каждой ошибке соответствует свой опознаватель. В таблице не используются двоичные числа, которые соответствуют номерам поврежденных разрядов,
так как тогда у нас получится код Хэмминга
Вектор ошибки 0000000001 0000000010 0000000100 0000001000 0000010000 0000100000 0001000000 0010000000 0100000000 1000000000 0000000011 0000000101 0000001001 0000010001 0000100001 0001000001 0010000001 0100000001 1000000001 0000000110 0000001010 0000010010 0000100010 0001000010 0010000010 0100000010 1000000010 0000001100 0000010100 0000100100 0001000100 0010000100 0100000100 1000000100 |
Опознаватели 0000001 0000010 0000100 0001000 0001111 0010000 0100000 0110011 1000000 1010101 0000011 0000101 0001001 0001110 0010001 0100001 0110010 1000001 1010100 0000110 0001010 0001101 0010010 0100010 0110001 1000010 1010111 0001100 0001011 0010100 0100100 0110111 1000100 1010001 |
Вектор Ошибки 0000011000 0000101000 0001001000 0010001000 0100001000 1000001000 0000110000 0001010000 0010010000 0100010000 1000010000 0001100000 0010100000 0100100000 1000100000 0011000000 0101000000 1001000000 0110000000 1010000000 1100000000 |
Опознаватели 0000111 0011000 0101000 0111011 1001000 1011101 0011111 0101111 0111100 1001111 1011010 0110000 0100011 1010000 1000101 0010011 1100000 1110101 1110011 1100100 0010101 |