Помехоустойчивое кодирование сообщений
Исследование особенностей кодирования данных в форме, удобной для использования в информационных системах и сетях. Расчет числа информационных и избыточных разрядов. Построение оптимального помехоустойчивого кода и кода для исправления двукратных ошибок.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 14.10.2014 |
| Размер файла | 28,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Концептуальное описание объекта
Цель и суть любого кодирования представление сообщений в форме удобной для их последующей обработки, а также для передачи хранения и выполнения арифметических и логических операций. Сообщения могут быть представлены в форме кодовых слов.
Идея помехоустойчивого кодирования состоит в том ,что кодер вносит избыточную информацию в виде правил кодирования добавляя дополнительные разряды помехоустойчивого кодового слова с последующей проверкой. Помехоустойчивые коды - одно из наиболее эффективных средств обеспечения высокой верности передачи дискретной информации.
Большое развитие теория помехоустойчивого кодирования получила с внедрением автоматизированных систем, у которых обработка принимаемой информации осуществляется без участия человека. Использование для обработки информации электронных цифровых вычислительных машин предъявляет очень высокие требования к верности передачи информации.
Под помехоустойчивыми или корректирующими кодами понимают коды, позволяющие обнаружить и устранить ошибки, происходящие при передаче из-за влияния помех.
Кодирование, с формальной точки зрения, является описанием данных в форме, удобной для использования в информационных системах и сетях. Оно осуществляется на каком-нибудь формальном языке. Этот процесс выполняется с участием программистов либо автоматически. Кодирование, при котором используется код, состоящий из букв, чисел и других знаков алфавита, именуется буквенно-цифровым кодированием. Кодирование может быть побуквеным, пословным. Для кодирования информации, представленной аналоговым сигналом, осуществить необходимо квантование и Аналого-Цифровое Преобразование (АЦП). Благодаря этому, получается дискретный сигнал, который представляется кодовыми комбинациями согласно некоторым правилам, называемым системой кодирования. Используемый код зависит от того, какая выполняется задача и какие требования поставлены перед способом представления информации.
Кодирование широко применяется в информационных сетях. Оно должно быть таким, чтобы обеспечивать максимально возможную скорость обработки данных и передачи данных, защищенность от искажений. С этой целью особо выделяют помехоустойчивое кодирование.
Широкую известность в сетях получило манчестерское кодирование, обеспечивающее не только передачу данных, но и синхронизацию этой передачи. Процесс, обратный кодированию, именуют декодированием. Изменение кодов осуществляется благодаря перекодированию данных.
Кодирование в сети осуществляется на различных уровнях. На физическом уровне оно необходимо потому, что абонентские системы работают с двоичными кодами, а в каналах и моноканалах часто используется троичный код. В результате кодирования физический уровень, часто, преобразует два физически раздельных сигнала: данных и синхронизации в единый самосинхронизирующийся поток битов. Для обеспечения безопасности данных осуществляется специальное кодирование, именуемое шифрованием.
кодирование информационный разряд помехоустойчивый
Построение оптимального помехоустойчивого кода
Исходная информация для построения кода:
Тип исправляемых ошибок -некореллированные
Кратность исправляемых ошибок - S =1 ;
Объем кода (число кодируемых сообщений) - Q = 35;
Расчет числа информационных и избыточных разрядов. Число информационных и избыточных разрядов определяется из соотношений
2k - 1 ? Q ;
2n - k - 1 ? n ;
n - k ;
где k - число информационных разрядов ;
n - число разрядов помехоустойчивого слова;
(n - k) - число избыточных разрядов;
отсюда k = 6; n =10; n - k = 4;
Построение таблицы опознавателей ошибок. Из таблицы видно, что каждой ошибке соответствует свой опознаватель. В таблице не используются двоичные числа, которые соответствуют номерам поврежденных разрядов, так как тогда у нас получится код Хэмминга.
|
Векторы ошибок |
Опознаватели ошибок |
|||||||||||
|
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 |
Построение проверочных равенств. Проверочное равенство представляет собой одно из преобразованных уравнений алгоритма кодирования.
Если при проверке дешифратором уравнений, определяющих данные избыточные разряды, произошло нарушение четности, то опознаватель окажется равным 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;
Построение алгоритма кодирования. Из системы уравнений приведенной выше составим следующее правило кодирования.
Избыточными разрядами будем считать такие разряды, которые в проверочных равенствах встречаются по одному разу.
a2 = a3 a5 a7 a8 a10
a4 = a1 a7 a10
a6 = a5 a8
a9 = a1 a3 a7 a8
Таблица кодирования.
|
Вход кодера |
Выход кодера |
|
|
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 |
Отсутствие ошибок в канале связи.
а) 010000 [ КОДЕР ] 0110100010 [КАНАЛ СВЯЗИ] 0110100010 [ ДЕКОДЕР ] 010000
б) 001001 [КОДЕР] 0001000011 [КАНАЛ СВЯЗИ] 0001000011 [ДЕКОДЕР] 001001
Ошибка опознана и исправлена верно.
а) 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
Ошибка опознана и исправлена неверно.
а) 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
Ошибка не опознана.
а) 000110 [ КОДЕР ] 0100110100 [КАНАЛ СВЯЗИ] 1110010101 [ ДЕКОДЕР ] 111011
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 1010100001
Декодирование:
0 1 1 0 1 1=0
1 0 0 1= 0
1 0 1 = 0
1 1 0 11= 0
Опознаватель 0000 => вектор ошибки 0000000000
Восстановление не требуется.
Выделение содержимого информационных разрядов 111011
б) 011010 [ КОДЕР ] 0111101110 [КАНАЛ СВЯЗИ] 0110010000 [ ДЕКОДЕР ] 011100
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0110010000
Декодирование:
11 1 1 0 = 0
0 11 0 = 0
1 1 0 = 0
0 1 1 0 0 = 0
Опознаватель 0000 => вектор ошибки 0000000000
Восстановление не требуется.
Выделение содержимого информационных разрядов 011100
Ошибка только обнаруживается
а) 011101 [ Кодер ]0111010011 [ канал связи ] 1110111111[дешифратор] ошибка
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 1001111111
Декодирование:
111 0 1 1=1
1 1 0 1=1
1 1 1=1
11 10=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;
Построение таблицы опознавателей ошибок.
Из таблицы видно, что каждой ошибке соответствует свой опознаватель. В таблице не используются двоичные числа, которые соответствуют номерам поврежденных разрядов, так как тогда у нас получится код Хэмминга
|
А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 |
Построение проверочных равенств. Проверочное равенство представляет собой одно из преобразованных уравнений алгоритма кодирования . Если при проверке дешифратором уравнений, определяющих данные избыточные разряды, произошло нарушение четности, то опознаватель окажется равным 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
Построение правила кодирования. Из системы уравнений приведенной выше составим следующее правило кодирования.
Избыточными разрядами будем считать такие разряды ,которые в проверочных равенствах встречаются по одному разу.
а1 = а5 а11
а4 = а3 а7
а6 = а2
а8 = а3 а5 а7
а9 = а2 а7 а11
а10 = а3
Построение кодирующей таблицы.
|
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 |
Построение таблицы декодирования.
|
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 |
Примеры неоптимального кодирования
Отсутствие ошибок в канале связи.
а) 01100 [ КОДЕР ] 00101011001 [КАНАЛ СВЯЗИ] 00101011001 [ ДЕКОДЕР ] 00110
б) 10001 [ КОДЕР ] 10000100011 [КАНАЛ СВЯЗИ] 10000100011 [ ДЕКОДЕР ] 10001
Ошибка опознана и исправлена верно.
а) 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
Ошибка опознана но исправлена неверно.
а)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
Ошибка не обнаруживается.
а) 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
Ошибка только обнаруживается
а) 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
010=1
11=0
1100=0
1100=0
11=0
Опознаватель 000011 => вектор ошибки отсутствует
На выходе дешифратора ошибка
Построение группового кода для исправления двукратных ошибок
Исходная информация для построения кода:
Тип исправляемых ошибок - некоррелированные
Кратность исправляемых ошибок - S =2 ;
Объем кода (число кодируемых сообщений) - Q =5;
Расчет числа информационных и избыточных разрядов.
Число информационных и избыточных разрядов определяется из соотношений
2k - 1 ? Q:
2n-k - 1 ? n2 + n /2:
где k - число информационных разрядов ;
n - число разрядов помехоустойчивого слова;
(n - k) - число избыточных разрядов;
отсюда k = 3; n =10; n - k = 7;
Построение таблицы опознавателей ошибок. Из таблицы видно, что каждой ошибке соответствует свой опознаватель. В таблице не используются двоичные числа, которые соответствуют номерам поврежденных разрядов, так как тогда у нас получится код Хэмминга
Таблица
|
Вектор ошибки 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 |
Построение проверочных равенств.
a1 a5 a8 a10
a2 a5 a8
a3 a5 a10
a4 a5
a6 a8 a10
a7 a8
a9 a10
a1 a5 a8 a10
a2 a5 a8
a3 a5 a10
a4 a5
a6 a8 a10
a7 a8
a9 a10
Построение алгоритма кодирования.
a1 = a5 a8 a10
a2 = a5 a8
a3 = a5 a10
a4 = a5
a6 = a8 a10
a7 =a8
Построение таблицы кодирования.
|
001 010 011 100 101 |
0000011111 0011100011 0011111100 1100100101 1100111010 |
Построение декодирующей таблицы.
|
0000011111 0011100011 0011111100 1100100101 1100111010 |
0000000000 |
|
|
0000011110 0011100010 0011111101 1100100100 1100111011 |
0000000001 |
|
|
1000011111 111100011 1011111100 0100100101 0100111010 |
1000000000 |
|
|
1000011110 1011100010 1011111101 0100100100 0100111011 |
1000000001 |
|
|
0000101111 0011010011 0011001100 1100010101 1100001010 |
0000110000 |
|
|
1100011111 1111100011 1111111100 0000100101 0000111010 |
1100000000 |
Примеры оптимального помехоустойчивого кодирования для двукратных ошибок
Передача слова без искажения помехой.
a) 010 [кодер] 0011100011 [ канал связи ] 0011100011 [дешифратор] 010
б) 100 [кодер] 1100100101 [ канал связи ] 1100100101 [дешифратор] 100
Передача кодового слова с искажением помехой в пределах корректирующей способности кода (однократная ошибка обнаруживается и исправляется)
а) 010 [кодер] 011100011 [ канал связи ] 0011100111 [дешифратор] 010
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0000000100
Декодирование:
1 0 1 0 = 0
1 0 1 = 0
1 0 0 = 1
0 0 =0
1 1 0 =0
1 1 =0
0 0 =0
Опознаватель 0000100 => вектор ошибки 0000000100
Восстановление
0011100111
0000000100
0011100011
Выделение содержимого информационных разрядов 010
б) 100 [кодер] 1100100101 [ канал связи ] 1100100111 [дешифратор] 100
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0000000100
Декодирование:
1 0 0 1 = 0
1 0 0 = 1
1 0 1 = 0
0 0 =0
1 0 1 =0
0 0 =0
Опознаватель 0000010 => вектор ошибки 0000000010
Восстановление
1100100111
0000000010
1100100101
Выделение содержимого информационных разрядов 100
Передача кодового слова с искажением помехой в пределах корректирующей способности кода (двукратная ошибка обнаруживается и исправляется)
а) 001 [кодер] 0000011111[ канал связи ] 0000010101 [дешифратор] 001
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0000001010
Декодирование:
1 1 0 0 = 0
0 1 0 = 1
1 1 0 = 0
0 1 =1
0 0 0 =0
0 0 =0
0 0 =0
Опознаватель 0001010 => вектор ошибки 0000001010
Восстановление
0000010101
0000001010
0000011111
Выделение содержимого информационных разрядов 001
б) 011 [кодер] 0011111100 [ канал связи ] 0011111001 [дефифратор] 011
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0000000101
Декодирование:
1 1 1 0 = 1
0 1 1 = 1
0 1 0 = 1
1 1 =0
1 1 0 =0
1 1 =0
0 0 =0
Опознаватель 0000101 => вектор ошибки 0000000101
Восстановление
0011111001
0000000101
0011111100
Выделение содержимого информационных разрядов 011
Внесение ошибки кратности большей чем корректирующая способность кода( ошибка обнаруживается и исправляется неправильно)
а) 001 [кодер] 0000011111[ канал связи ]0000100011 [дешифратор] 010
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0000111100
Декодирование:
1 0 0 0 = 1
1 0 0 = 1
0 0 0 = 0
0 0 =0
1 0 0 =1
0 0 =0
0 0 =0
Опознаватель 0010011 => вектор ошибки 0010100000
Восстановление
0000100011
0011000000
0011100011
Выделение содержимого информационных разрядов 010
б) 010 [кодер] 0011100011[ канал связи ] 0100100001 [дешифратор] 100
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0111000010
Декодирование:
1 0 0 0 = 1
0 0 0 = 0
0 0 0 = 0
0 0 =0
1 0 0 =1
0 0 =0
0 0 =0
Опознаватель 1010001 => вектор ошибки 1000000100
Восстановление
0100100001
1000000100
1100100101
Выделение содержимого информационных разрядов 100
Ошибка не обнаруживается.
а) 101 [кодер] 1100111010[ канал связи ]0000011111 [дешифратор] 100
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 1100100101
Декодирование:
1 1 0 0 = 0
1 0 1 = 0
1 1 0 = 0
1 1 =0
0 0 0 =0
0 0 =0
0 0 =0
Опознаватель 0000000 => вектор ошибки 0000000000
Восстановление не требуется.
Выделение содержимого информационных разрядов 100.
б) 100 [кодер] 1100100101[ канал связи ]1111000110 [дешифратор] 011
Кодирование : находим в таблице кодирования кодовое слово соответствующее входному. Искажение помехой: 0000000101
Декодирование:
0 0 1 1 = 0
1 0 1 = 0
1 0 1 = 0
0 0 =0
0 1 1 =0
1 1 =0
1 1 =0
Опознаватель 0000000 => вектор ошибки 0000000000
Восстановление не требуется.
Выделение содержимого информационных разрядов 010
Ошибка только обнаруживается.
а) 010 [кодер] 0011100011[ канал связи ]0110001100 [дешифратор] ошибка
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0101101111
Декодирование:
0 0 1 0 = 1
0 0 1 = 1
1 0 0 = 1
1 0 =1
0 1 0 =1
0 1 =1
1 0 =1
Опознаватель 1111111 => вектор ошибки отсутствует
Восстановление не требуется.
На выходе декодера сигнал ошибки.
б) 011 [кодер] 0011111100[ канал связи ]0110011100 [дешифратор] ошибка
Кодирование: находим в таблице кодирования кодовое слово соответствующее входному.
Искажение помехой: 0101100000
Декодирование:
0 1 1 0 = 0
0 1 1 = 0
1 1 0 = 0
1 1 =0
0 1 0 =1
0 1 =1
1 0 =1
Опознаватель 1110000 => вектор ошибки отсутствует
Восстановление не требуется.
На выходе декодера сигнал ошибки.
Размещено на Allbest.ru
...Подобные документы
Число информационных разрядов кода. Вектор ошибок как n-разрядная двоичная последовательность, имеющая единицы во всех разрядах, подвергшихся искажению, и нули в разрядах. Функциональные и принципиальные схемы кодирующего и декодирующего устройств.
задача [428,4 K], добавлен 28.04.2009Общее число неповторяющихся сообщений. Вычисление скорости передачи информации и пропускной способности каналов связи. Определение избыточности сообщений и оптимальное кодирование. Процедура построения оптимального кода по методике Шеннона-Фано.
курсовая работа [59,4 K], добавлен 17.04.2009Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.
курсовая работа [212,6 K], добавлен 25.02.2009Генерация порождающего полинома для циклического кода. Преобразование порождающей матрицы в проверочную и обратно. Расчет кодового расстояния для линейного блокового кода. Генерация таблицы зависимости векторов ошибок от синдрома для двоичных кодов.
доклад [12,6 K], добавлен 11.11.2010Кодирование и декодирование, преобразование дискретного сообщения в дискретный сигнал. Построение математической модели корректирующего кода. Образующая матрица информационного кода. Модульная структура программы. Спецификация на программные модули.
курсовая работа [98,9 K], добавлен 28.11.2014Помехоустойчивое кодирование, правильность передачи информации. Устранение ошибок в симплексных каналах связи с помощью корректирующих кодов. Способы обнаружения ошибок - контрольное суммирование, проверка на нечетность. Применение циклических кодов.
реферат [28,1 K], добавлен 03.08.2009Определение среднего количества информации. Зависимость между символами матрицы условных вероятностей. Кодирование методом Шеннона–Фано. Пропускная способность канала связи. Эффективность кодирования сообщений методом Д. Хаффмана, характеристика кода.
контрольная работа [94,6 K], добавлен 04.05.2015Сущность линейного и двухмерного кодирования. Схема проверки подлинности штрих-кода. Анализ способов кодирования информации. Расчет контрольной цифры. Штриховое кодирование как эффективное направление автоматизации процесса ввода и обработки информации.
презентация [1,1 M], добавлен 05.10.2014Источники сообщений, сигналы и коды, примеры применения знания основ теории информации для практических целей. Расчет информационных характеристик и согласование дискретного источника с дискретным каналом без шума и с шумом, эффективное кодирование.
курсовая работа [179,6 K], добавлен 13.11.2009Описание и особенности некоторых алгоритмов архивации. Построение кода Хаффмана. Динамический алгоритм построения кода Хаффмана. Обратное восстановление текста. Способы двухступенчатого кодирования информации. Практическая реализация алгоритма LZ77.
курсовая работа [51,7 K], добавлен 24.12.2012Жизненный цикл информационных систем, методологии и технологии их проектирования. Уровень целеполагания и задач организации, классификация информационных систем. Стандарты кодирования, ошибки программирования. Уровни тестирования информационных систем.
презентация [490,2 K], добавлен 29.01.2023Исследование принципа действия поэлементной синхронизации с добавлением и вычитанием импульсов. Характеристика кодирования в системах ПДС, классификации кодов, построения кодера и декодера циклического кода. Расчет параметров системы с ОС и ожиданием.
курсовая работа [2,8 M], добавлен 08.12.2011Использование принципа формирования кода Хэмминга в процессе отладки ошибки. Сложение двоичного числа по модулю в программе и получение кода ошибки для определения разряда, в котором она содержится. Соответствие ошибки определенному разряду операнда.
лабораторная работа [8,0 K], добавлен 29.06.2011Необходимость защиты информации. Виды угроз безопасности ИС. Основные направления аппаратной защиты, используемые в автоматизированных информационных технологиях. Криптографические преобразования: шифрование и кодирование. Прямые каналы утечки данных.
курсовая работа [72,1 K], добавлен 22.05.2015Преобразование чисел из естественной формы в нормализованную. Алгоритм нормализации числа. Способы кодирования чисел и действия над ними. Особенности прямого, дополнительного, смещенного и обратного кода. Понятие вещественных чисел, их представление.
презентация [42,6 K], добавлен 14.06.2011Сущность метода перестановочного декодирования. Особенности использования метода вылавливания ошибок. Декодирование циклического кода путем вылавливания ошибок. Распознавание пакетов ошибок как особенность циклических кодов. Вычисление вектора ошибок.
доклад [20,3 K], добавлен 24.05.2012Кодирование как процесс представления информации в виде кода. Кодирование звуковой и видеоинформации, характеристика процесса формирования определенного представления информации. Особенности универсального дружественного интерфейса для пользователей.
контрольная работа [20,3 K], добавлен 22.04.2011Запись прямого и обратного кода для числа 10010 и -10010. Получение дополнительного кода числа для 16-разрядной ячейки. Перевод в двоичную систему счисления десятичных чисел: 10, 45, 7, 33. Запись в обратном и дополнительном кодах числа -67, -43, -89.
практическая работа [13,7 K], добавлен 19.04.2011Схема организационной структуры управления информационных и аналитических технологий аппарата администрации. Математическая постановка задачи классификации информационных сообщений СМИ. Описание информационного обеспечения на примере АИС "Классификатор".
дипломная работа [677,2 K], добавлен 28.07.2009Методы арифметического кодирования. Основные функции программ, реализующие алгоритмы кодирования по методам Хаффмана, Голомба, Фибоначчи и Элиаса. Разработка программно-аппаратных средств оптимального арифметического кодирования и их экономический расчет.
дипломная работа [1,1 M], добавлен 26.05.2012
