Автор работы: Пользователь скрыл имя, 27 Мая 2012 в 16:58, контрольная работа
В середине 40-х годов Ричард Хемминг работал в знаменитых Лабораториях Белла на счётной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки,скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машине с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую.
Код Хемминга………………………………………………………..2
История………………………………………………………………………….2
Самоконтролирующиеся коды……………………………………………2
Самокорректирующиеся коды…………………………………………….3
Код Грея…………………………………………………………….14
Код Грея, рефлексный двоичный код…...........................................14
Преобразование двоичного кода в код Грея……………………......14
Преобразование кода Грея в двоичный код…………………………15
Генерация кодов Грея……………………………………………………...16
Турбо код……………………………………………………………17
История………………………………………………………………………...17
Кодирование………………………………………………………………….18
Кодовая скорость……………………………………………………….......19
Декодирование……………………………………………………………….20
Одна итерация итеративного турбо-декодера при двухкаскадном кодировании…………………………………………………………………..21
Трёхитерационный турбо декодер при двухкаскадном кодировании............................................................................................21
Преимущества и недостатки турбо-кодов……………………………..21
Примение турбо - кодов……………………………………………………22
| p4 | p3 | p2 | p1 | ||
| В двоичном представлении | 0 | 1 | 0 | 1 | |
| В десятичном представлении | 4 | 1 | Σ = 5 |
Вывод: ошибка произошла в 5-м разряде Истинное кодовое слово : 1 0 0 0 1 1 0 0 1 0 1 Ошибочное кодовое слово : 1 0 1 0 1 0 0 0 1 0 1 Исправленное кодовое слово : 1 0 1 0 0 0 0 0 1 0 1 Результат получается ещё более отдаленным от правильного, чем принятый код. Исправление кода по общему правилу не только не улучшило, но даже ухудшило бы дело.
Можно построить и
такой код, который обнаруживал
бы двойные ошибки и исправлял
одиночные. Для этого к
Например, код Хеминга с m=7 и k=4 Пусть информационное кодовое слово - 0110101
| № разряда: | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | Second Parity |
| Распределение контрольных и информационных разрядов | p1 | p2 | d1 | p3 | d2 | d3 | d4 | p4 | d5 | d6 | d7 | |
| Информационное кодовое слово: | 0 | 1 | 1 | 0 | 1 | 0 | 1 | |||||
| p1 | 1 | 0 | 1 | 0 | 1 | 1 | ||||||
| p2 | 0 | 0 | 1 | 0 | 0 | 1 | ||||||
| p3 | 0 | 1 | 1 | 0 | ||||||||
| p4 | 0 | 1 | 0 | 1 | ||||||||
| Кодовое слово с контрольными разрядами: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
При этом могут быть следующие случаи.
1. В принятом коде
в целом и по всем контрольным
группам количество единиц
| № разряда: | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | Контроль по четности в группе | Контрольный бит | Контроль по четности в целом | Контрольный бит в целом |
| Распределение контрольных и информационных разрядов | p1 | p2 | d1 | p3 | d2 | d3 | d4 | p4 | d5 | d6 | d7 | ||||
| Переданное кодовое слово: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | ||||
| Принятое кодовое слово: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | ||||
| p1 | 1 | 0 | 1 | 0 | 1 | 1 | Pass | 0 | |||||||
| p2 | 0 | 0 | 1 | 0 | 0 | 1 | Pass | 0 | |||||||
| p3 | 0 | 1 | 1 | 0 | Pass | 0 | |||||||||
| p4 | 0 | 1 | 0 | 1 | Pass | 0 | 1 | Pass |
| p4 | p3 | p2 | p1 | ||
| В двоичном представлении | 0 | 0 | 0 | 0 | |
| В десятичном представлении | Σ = 0 |
2. В принятом коде
в целом количество единиц
нечетно, но во всех
| № разряда: | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | Контроль по четности в группе | Контрольный бит | Контроль по четности в целом | Контрольный бит в целом |
| Распределение контрольных и информационных разрядов | p1 | p2 | d1 | p3 | d2 | d3 | d4 | p4 | d5 | d6 | d7 | ||||
| Переданное кодовое слово: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | ||||
| Принятое кодовое слово: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | ||||
| p1 | 1 | 0 | 1 | 0 | 1 | 1 | Pass | 0 | |||||||
| p2 | 0 | 0 | 1 | 0 | 0 | 1 | Pass | 0 | |||||||
| p3 | 0 | 1 | 1 | 0 | Pass | 0 | |||||||||
| p4 | 0 | 1 | 0 | 1 | Pass | 0 | 0 | Fail |
| p4 | p3 | p2 | p1 | ||
| В двоичном представлении | 0 | 0 | 0 | 0 | |
| В десятичном представлении | Σ = 0 |
3. В принятом коде
в целом и в некоторых из
контрольных групп количество
единиц нечетно. Третий случай
— одиночной ошибки в каком-
| № разряда: | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | Контроль по четности в группе | Контрольный бит | Контроль по четности в целом | Контрольный бит в целом |
| Распределение контрольных и информационных разрядов | p1 | p2 | d1 | p3 | d2 | d3 | d4 | p4 | d5 | d6 | d7 | ||||
| Переданное кодовое слово : | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | ||||
| Принятое кодовое слово: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | ||||
| p1 | 1 | 0 | 1 | 0 | 1 | 0 | Fail | 1 | |||||||
| p2 | 0 | 0 | 1 | 0 | 0 | 0 | Fail | 1 | |||||||
| p3 | 0 | 1 | 1 | 0 | Pass | 0 | |||||||||
| p4 | 0 | 1 | 0 | 0 | Fail | 1 | 1 | Fail |
| p4 | p3 | p2 | p1 | ||
| В двоичном представлении | 1 | 0 | 1 | 1 | |
| В десятичном представлении | 8 | 2 | 1 | Σ = 11 |
Из таблицы следует, что ошибка произошла в 11-м разряде и что её можно исправить.
4. В принятом коде
в целом количество единиц
четно, но в некоторых
| № разряда: | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | Контроль по четности в группе | Контрольный бит | Контроль по четности в целом | Контрольный бит в целом |
| Распределение контрольных и информационных разрядов | p1 | p2 | d1 | p3 | d2 | d3 | d4 | p4 | d5 | d6 | d7 | ||||
| Переданное кодовое слово: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | ||||
| Принятое кодовое слово: | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | ||||
| p1 | 1 | 1 | 1 | 0 | 1 | 1 | Fail | 1 | |||||||
| p2 | 0 | 1 | 0 | 0 | 0 | 1 | Pass | 0 | |||||||
| p3 | 0 | 1 | 0 | 0 | Fail | 1 | |||||||||
| p4 | 0 | 1 | 0 | 1 | Pass | 0 | 1 | Pass |