Автор работы: Пользователь скрыл имя, 13 Октября 2014 в 18:01, реферат
Цель и суть любого кодирования представление сообщений в форме удобной для их последующей обработки, а также для передачи хранения и выполнения арифметических и логических операций. Сообщения могут быть представлены в форме кодовых слов.
Идея помехоустойчивого кодирования состоит в том ,что кодер вносит избыточную информациию в виде правил кодирования добавляя дополнительные разряды помехоустойчивого кодового слова с последующей проверкой.
Концептуальное описание объекта.
Цель и суть любого кодирования представление сообщений в форме удобной для их последующей обработки, а также для передачи хранения и выполнения арифметических и логических операций. Сообщения могут быть представлены в форме кодовых слов.
Идея помехоустойчивого
Помехоустойчивые коды – одно из наиболее эффективных средств обеспечения высокой верности передачи дискретной информации.
Большое развитие теория помехоустойчивого кодирования получила с внедрением автоматизированных систем, у которых обработка принимаемой информации осуществляется без участия человека. Использовние для обработки информации электронных цифровых вычислительных машин предъявляет очень высокие требования к верности передачи информации.
Под помехоустойчивыми или корректирующими кодами понимают коды, позволяющие обнаружить и устранить ошибки, происходящие при передаче из-за влияния помех.
Кодирование, с формальной точки зрения, является описанем данных в форме, удобной для использования в информационных системах и сетях. Оно осуществляется на каком-нибудь формальном языке. Этот процесс выполняется с участием программистов либо автоматически. Кодирование, при котором используется код, состоящий из букв, чисел и других знаков алфавита, именуется буквенно-цифровым кодированием. Кодирование может быть побуквеным, пословным.
Для кодирования информации, представленной аналоговым сигналом, осуществить необходимо квантование и Аналого-Цифровое Преобразование (АЦП). Благодаря этому, получается дискретный сигнал, который представляется кодовыми комбинациями согласно некоторым правилам, называемым системой кодирования. Используемый код зависит от того, какая выполняется задача и какие требования поставлены перед способом представления информации.
Кодирование широко применяется в информационных сетях. Оно должно быть таким, чтобы обеспечивать максимально возможную скорость обработки данных и передачи данных, защищенность от искажений. С этой целью особо выделяют помехоустойчивое кодирование.
Широкую известность в сетях получило манчестерское кодирование, обеспечивающее не только передачу данных, но и синхронизацию этой передачи. Процесс, обратный кодированию, именуют декодированием. Изменение кодов осуществляется благодаря перекодированию данных.
Кодирование в сети осуществляется на различных уровнях. На физическом уровне оно необходимо потому, что абонентские системы работают с двоичными кодами, а в каналах и моноканалах часто используется троичный код. В результате кодирования физический уровень, часто, преобразует два физически раздельных сигнала: данных и синхронизации в единый самосинхронизирующийся поток битов. Для обеспечения безопасности данных осуществляется специальное кодирование, именуемое шифрованием.
Построение оптимального помехоустойчивого кода
Исходная информация для построения кода:
Тип исправляемых ошибок –некореллированные
Кратность исправляемых ошибок – S =1 ;
Объем кода (число кодируемых сообщений) - Q = 35;
Число информационных и избыточных разрядов определяется из соотношений
2k – 1 ≥ Q ;
2n – k – 1 ≥ n ;
n – k ;
где k – число информационных разрядов ;
n - число разрядов помехоустойчивого слова;
(n – k) – число избыточных разрядов;
отсюда k = 6; n =10; n – k = 4;
2.Построение таблицы опознавателей ошибок.
Из таблицы видно, что каждой ошибке соответствует свой опознаватель. В таблице не используются двоичные числа, которые соответствуют номерам поврежденных разрядов,
так как тогда у нас получится код Хэмминга.
Векторы ошибок |
Опознаватели ошибок |
||||||||||
A10 |
A9 |
A8 |
A7 |
A6 |
A5 |
A4 |
A3 |
A2 |
A1 | ||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1010 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0001 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0011 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1000 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0101 |
5 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0100 |
6 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1011 |
7 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0111 |
8 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0010 |
9 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1001 |
10 |
2.Построение проверочных равенств.
Проверочное равенство представляет собой одно из преобразованных уравнений алгоритма кодирования . Если при проверке дешифратором уравнений, определяющих данные избыточные разряды, произошло нарушение четности, то опознаватель окажется равным 1.
Разряды опознавателя определяются следующими проверочными равенствами:
a2 Ú a3 Ú a5 Ú a7 Ú a8 Ú a10
a1 Ú a3 Ú a7 Ú a8 Ú a9
a5 Ú a6 Ú a8
a1 Ú a4 Ú a7 Ú a10
Запишем проверочные равенства в виде системы уравнений:
a2 Å a3 Å a5 Å a7 Å a8 Å a10 = 0;
a1 Å a3 Å a7 Å a8 Å a9 = 0;
a5 Å a6 Å a8 = 0;
a1 Å a4 Å a7 Å a10 = 0;
4. Построение алгоритма кодирования
Из системы уравнений приведенной выше составим следующее правило кодирования.
Избыточными разрядами будем считать такие разряды ,которые в проверочных равенствах встречаются по одному разу.
a2 = a3 Å a5 Å a7 Å a8 Å a10
a4 = a1 Å a7 Å a10
a6 = a5 Å a8
a9 = a1 Å a3 Å a7 Å a8
5. Таблица кодирования.
Вход кодера |
Выход кодера |
000001 000010 000011 000100 000101 000110 000111 001000 001001 001010 001011 001100 001101 001110 001111 010000 010001 010010 010011 010100 010101 010110 010111 011000 011001 011010 011011 011100 011101 011110 011111 100000 100001 100010 100011 |
0100001001 0100000110 0000001111 0000110010 0100111011 0100110100 0000111101 0101001010 0001000011 0001001100 0101000101 0101111000 0001110001 0001111110 0101110111 0110100010 0010101011 0010100100 0110101101 0110010000 0010011001 0010010110 0110011111 0011101000 0111100001 0111101110 0011100111 0011011010 0111010011 0111011100 0011010101 1000001010 1100100011 1100101100 1000000101 |
Таблица декодирования
0100001001 0100000110 0000001111 0000110010 0100111011 0100110100 0000111101 0101001010 0001000011 0101000101 0101111000 0001110001 0001111110 0101110111 0110100010 0010101011 0010100100 0110101101 0110010000 0010011001 0010010110 0110011111 0011101000 0111100001 0111101110 0011100111 0011011010 0111010011 0111011100 0011010101 1000001010 1100100011 1100101100 1000000101 |
00000000000
|
0100001000 0100000111 0000001110 0000110011 0100111010 0100110101 0000111100 0101001011 0001000010 0101000100 0101111001 0001110000 0001111111 0101110110 0110100011 0010101010 0010100101 0110101100 0110010001 0010011000 0010010111 0110011110 0011101001 0111100000 0111101111 0011100110 0011011011 0111010010 0111011101 0011010100 1000001011 1100100010 1100101101 1000000100 |
00000000001 |
0100001011 0100000100 0000001101 0000110000 0100111001 0100110110 0000111111 0101001000 0001000001 0101000111 0101111010 0001110011 0001111100 0101110101 0110100000 0010101001 0010100110 0110101111 0110010010 0010011011 0010010100 0110011101 0011101010 0111100011 0111101100 0011100101 0011011000 0111010001 0111011110 0011010111 1000001000 1100100001 1100101110 1000000111 |
00000000010 |
0100001001 0100000010 0000001011 0000110110 0100111111 0100110000 0000111001 0101001110 0001000111 0101000001 0101111100 0001110101 0001111010 0101110011 0110100110 0010101111 0010100000 0110101001 0110010100 0010011101 0010010010 0110011011 0011101100 0111100101 0111101010 0011100011 0011011110 0111010111 0111011000 0011010001 1000001110 1100100111 1100101000 1000000001 |
00000000100
|
0100101001 0100100110 0000101111 0000010010 0100011011 0100010100 0000011101 0101101010 0001100011 0101100101 0101011000 0001010001 0001011110 0101010111 0110000010 0010001011 0010000100 0110001101 0110110000 0010111001 0010110110 0110111111 0011001000 0111000001 0111001110 0011000111 0011111010 0111110011 0111111100 0011110101 1000101010 1100000011 1100001100 1000100101 |
00001000000 |
0110001001 0110000110 0010001111 0010110010 0110111011 0110110100 0010111101 0111001010 0011000011 0111000101 0111111000 0011110001 0011111110 0111110111 0100100010 0000101011 0000100100 0100101101 0100010000 0000011001 0000010110 0100011111 0001101000 0101100001 0101101110 0001100111 0001011010 0101010011 0101011100 0001010101 1010001010 1110100011 1110101100 1010000101 |
0010000000 |
1. Отсутствие ошибок в канале связи.
а) 010000 [ КОДЕР ] 0110100010 [КАНАЛ СВЯЗИ] 0110100010 [ ДЕКОДЕР ] 010000
б) 001001 [КОДЕР] 0001000011 [КАНАЛ СВЯЗИ] 0001000011 [ДЕКОДЕР] 001001
2. Ошибка опознана и исправлена верно.
а) 001011 [ КОДЕР ] 0101000101 [КАНАЛ СВЯЗИ] 0101000001 [ ДЕКОДЕР ] 001011
Кодирование: находим
в таблице кодирования кодовое
слово соответствующее
Искажение помехой: 0000000100
Декодирование:
0 Å 0 Å 0 Å 1 Å 0 Å 0 =1
0 Å 0 Å 1 Å 0 =1
0 Å0 Å 0 =0
0 Å0 Å 1Å 0 Å 1=0
Опознаватель 0011 => вектор ошибки 0000000100
Восстановление
0101000001
Å 0000000100
0101000100
Выделение содержимого информационных разрядов 001011
б) 001010 [ КОДЕР ] 0001001100 [КАНАЛ СВЯЗИ] 0001011100 [ ДЕКОДЕР ] 001010
Кодирование: находим
в таблице кодирования кодовое
слово соответствующее
Искажение помехой: 0000010000
Декодирование:
0 Å 1 Å 1 Å 1 Å 0 Å 0 = 1
0 Å 1 Å 1 Å 0 = 0
1 Å 0 Å 0 = 1
0 Å 1 Å 1 Å 0 Å 0= 0
Опознаватель 0101 => вектор ошибки 0000010000
Восстановление
0001011100
Å 0000010000
0001001100
Выделение содержимого информационных разрядов 001010
3.Ошибка опознана и исправлена неверно.
а) 010001 [ КОДЕР ] 0010101011 [КАНАЛ СВЯЗИ] 0110101111 [ ДЕКОДЕР ] 0110101101
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0100000100
Декодирование:
1 Å 1 Å 0 Å 0 Å 1 Å 0 =1
1 Å 1Å 0 Å 0=0
0 Å 1 Å 1 = 0
1 Å 1 Å 0 Å 1 Å 1=0
Опознаватель 0001 => вектор ошибки 0000000010
Восстановление
0110101111
Å 0000000010
0110101101
Выделение содержимого информационных разрядов 010011
б) 011100 [ КОДЕР ] 0011011010 [КАНАЛ СВЯЗИ] 1000100000 [ ДЕКОДЕР ] 1001111010
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 1000100000
Декодирование:
1 Å 0 Å 1 Å 1 Å 1 Å 1 = 1
0 Å 0 Å 1 Å 0=1
0 Å 0 Å 0 =0
0 Å 0 Å 1Å 0 Å 1=0
Опознаватель 0011 => вектор ошибки 0000000100
Восстановление
0101000001
Å 0000000100
0101000100
Выделение содержимого информационных разрядов 011100
4.Ошибка не опознана.
а) 000110 [ КОДЕР ] 0100110100 [КАНАЛ СВЯЗИ] 1110010101 [ ДЕКОДЕР ] 111011
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 1010100001
Декодирование:
0 Å 1Å 1Å 0 Å 1 Å 1=0
1 Å 0 Å 0 Å 1= 0
1 Å 0 Å 1 = 0
1 Å 1 Å 0 Å 1Å1= 0
Опознаватель 0000 => вектор ошибки 0000000000
Восстановление не требуется.
Выделение содержимого информационных разрядов 111011
б) 011010 [ КОДЕР ] 0111101110 [КАНАЛ СВЯЗИ] 0110010000 [ ДЕКОДЕР ] 011100
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0110010000
Декодирование:
1Å1Å 1 Å1Å 0 = 0
0 Å 1Å1Å 0 = 0
1 Å 1Å 0 = 0
0 Å 1 Å 1 Å 0 Å 0 = 0
Опознаватель 0000 => вектор ошибки 0000000000
Восстановление не требуется.
Выделение содержимого информационных разрядов 011100
5. Ошибка только обнаруживается
а) 011101 [ Кодер ]0111010011 [ канал связи ] 1110111111[дешифратор] ошибка
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.