ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ (применение)
Хранение информации с высокой плотностью записи –CD-
ROM, DVD
Передача данных при ограниченной мощности сигнала –
спутниковая и мобильная связь
Передача информации по сильно зашумленным каналам
– высокоскоростные проводные линии связи,
мобильная связь
Передача данных по каналам связи с повышенными
требованиями к надежности информации –
Средняя вероятность ошибки одного бита передаваемой информации (BER – bit error rate):
мобильные каналы связи 10-2 мроводные каналы связи 10-5 волоконноптические каналы 10-12
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ (за счет
избыточности кода):
• Обнаружение ошибок последующим запросом на повторную передачу ошибочно принятой информации ( ARR – automatic repeat request) (самоконтроллирующиеся коды)
•Локализация ошибок (FEC – forward error correction) (самоисправляющиеся коды)
ПРИМЕР ПРИЕМА ИСКАЖЕННОГО СООБЩЕНИЯ
Исходное сообщение: 00010100
Искажения при передаче сообщения - замена в двоичном сообщении 0 на 1 и\или наоборот,
Принятое сообщение 1: 00110100замена 1 на 0
Принятое сообщение 2: 00000100
Принятое сообщение 3: 00101100
ПОМЕХОУСТОЙЧИВОЕ
КОДИРОВАНИЕ
Из-за помех (шума) сообщение в процессе передачи может исказиться. Может произойти из-за магнитной бури, молнии, метеоритного дождя, случайного искажения звука в радиопередаче, плохой печати изображения или текста, плохой слышимости …
Для защиты от случайных воздействий при кодировании сообщения добавляют контролируемую избыточность. Она позволяет обнаружить и/или исправить ошибки, возникшие из-за зашумленности
Самоконтроллирующийсяканала. код – код,
позволяющий автоматически обнаруживать наиболее вероятные ошибки.
Самокорректирующийся код - код, |
|
позволяющий автоматически исправлять |
|
ошибки. |
23 |
|
ПОМЕХОУСТОЙЧИВОЕ
САМОКОНТРОЛИРУЮЩИЕСЯКОДИРОВАНИЕ
КОДЫ 1.Код с битом контроля чётности
1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1…
1 0 0 1 1 |
0 0 1 0 1 0 10 1 0 1 0 |
00 1 0 |
|
1 0 1 |
1 0 1 |
1 0 0 |
1… |
1 0 0 0 1 |
01 0 0 1 0 |
1 1 1 0 1 1 |
00 1 0 |
1 0 1 |
1 0 1 |
1 0 1 |
1… |
Одиночная |
Двойная |
Тройная |
|
ошибка |
ошибка |
ошибка |
|
Если число единиц в 8-ми битовом блоке чётно, |
|
проверочный бит равен 1, иначе – 0. Код |
|
обнаруживает одиночные ошибки и групповые с |
24 |
|
ПОМЕХОУСТОЙЧИВОЕ
КОДИРОВАНИЕ
ПРИМЕРЫ
1. Кодируемое (исходное) слово:
10111101 Оно содержит 6 единиц, бит чётности для него
равен 1.
Слово кода с проверкой четности для него: 101111011
2. Кодируемое (исходное) слово:
01110011
Оно содержит 5 единиц, бит чётности для него равен 0.
Слово кода с проверкой четности для него: 011100110
25
КОД С КОНТРОЛЬНОЙ
|
СУММОЙ |
|
|
|
|
|
|
|
Алгоритм: |
||
|
|
||||
|
|
|
|
1. Сложить все |
|
|
|
|
|
цифры, которые |
|
|
|
|
|
стоят на четных |
|
|
|
|
|
местах: |
|
|
|
|
|
6+1+4+0+1+9=21. |
|
|
|
|
|
2. Полученную |
|
|
|
|
|
сумму умножить на |
|
|
|
|
|
3: 21x3=63. |
|
|
|
|
|
3. Сложить все |
|
|
|
|
|
цифры, которые |
|
|
|
|
|||
|
|
|
|
стоят на нечетных |
|
|
4. Сложить числа, полученные |
местах, без |
|
||
|
контрольной |
|
|||
63+19=82. |
|
|
цифры: |
|
|
|
5. От полученной суммы |
|
4+0+5+6+2+2=19. |
|
|
|
получим 2. |
|
|
|
|
6. Из 10 вычесть полученное в пункте 5 число: 10- |
|
2=8. |
26 |
|
|
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
САМОКОРРЕКТИРУЮЩИЕСЯ КОДЫ Код с повторением
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 … |
111 |
111 |
000 |
111 |
000 |
|
1 |
1 0 0 000 |
111 |
||||||
111 000 111 |
… |
|
|
|
|
|
||
101 010 000 101 110 111 000 111 010 111 000 1110 … 1 1 1 0 1 0 1 0 1 …
Алгоритм
Кодирование: каждый символ исходного слова заменяется блоком из n
(n-нечетное) точно таких символов.
При декодировании n-знаковый блок заменяется на символ 1 или 0 решением «большинства символов» 27
блока.
ПРИМЕР равномерного кода
Сообщение Алисы:
NNWNNWWSSWWNNN NWWN
А={E,W,S
,N}
Алфавит равномерного кода:
А1={00,01,10,11}
Одиночная ошибка при таком кодировании приводит к катастрофе!
Начало сообщения Алисы: N N W N
Начало сообщенияN .Алисы. . (закодированное):
1111011111. . .
ПРИМЕР. Самоконтролирующийся код
Сообщение Алисы:
NNWNNWWSSWWNNN NWWN
А={E,W,S
,N}
Алфавит избыточного равномерного кода: А1=
{000,011,101,110}
Такой код обнаруживает одиночную
ошибку! Начало сообщения Алисы: NNWNN …
Начало сообщения Алисы (закодированное):
110110011110110 …
ПРИМЕР. Самокорректирующийся код
Сообщение Алисы:
NNWNNWWSSWWNNN NWWN
А={E,W,S
,N}
Алфавит избыточного равномерного кода:
А1= {00000,01101,10110,11011}
Такой код локализует одиночную ошибку!
Начало сообщения Алисы: NNWNN …
Начало сообщения Алисы (закодированное):
110111101110110110111
1011 …