LEC05. Основы помехоустойчивого кодирования
.pdf
НИУИТМО.КафедраВТ
Информатика(2014/2014)
Группы 1100, 1101, 1103, 1105, 1106, 1652. Балакшин П.В., Соснин В.В.
Лекция5. Основы помехоустойчивого кодирования
Гурупомехоустойчивого кодирования
РичардУэсли Хэмминг
(1915-1998)
1950 г.
Помехоустойчивость кодированияобеспечивается за счетвведения избыточностив кодовые комбинации.
Хобби – расчётпоследствий взрываатомнойбомбы.
2
Чтоделатьс ошибками припередаче
•Использоватьполученныеданныебез проверки наошибки.
•Обнаружитьошибку, выполнитьзапрос повторной передачиповреждённого блока.
•Обнаружитьошибку и отбросить повреждённый блок.
•Обнаружитьи исправить ошибку (forwarderror correction).
3
Помехоустойчивыекоды
Блочные Непрерывные
Фиксированные блоки информации длиной k символовпреобразуются вблоки длиной n символов (независимо друг от друга)
Передаваемаяинформационная последовательность не разделяется на блоки
Сверточные
|
Неравномерные |
Корректирующиеошибки |
|
|
коды;работают |
||
Равномерные КодМорзе:редко |
с непрерывным потоком |
||
n - константа |
используемые |
данных, кодируя их при |
|
символы кодируются |
помощирегистровсдвига |
||
|
|||
|
большим количеством |
с линейной обратной |
|
|
точек и тире |
связью |
|
4
Равномерные
Разделимые |
Неразделимые |
|
Кодыс постоянной плотностью |
|
единиц:информационные |
|
и проверочные разряды неразделимы |
Систематические |
Несистематические |
(линейные) |
Кодыс контрольным |
1. Биты |
суммированием |
чётности/нечётности |
|
2.Циклические коды
3.КодыБЧХ
4.КодыРС (Рида-Соломона)
5.КодХэмминга
5
Показателикодирования:
Помехоустойчивыйкод характеризуется: i– число информационныхразрядов
r – число проверочных(контрольных)разрядов n– общеечисло разрядов
Коэффициентизбыточности:КИ = r / n
6
Контрольнаясумма (check sum)— некотороечисло,
рассчитанноепутём применения определённого алгоритмак набору данныхи используемоедля проверки целостностиэтого набора данныхпри их передачеили хранении.
Битчётности– частный случай контрольной суммы,представляющий из себя 1 контрольныйбит, используемыйдля проверки общейчётности количестваединичныхбитов в двоичномчисле.
Контрольпо паритету – Parity flag
Методрасчётабита чётности– суммированиепо |
|
модулю2 всех битовчисла. |
7 |
|
Систематическиекоды:
- линейныеоперации над информационными символами
Самоконтролирующиесякоды:
- добавочныйразряд, счетчик по модулю 2
Самокорректирующиесякоды:
- несколько добавочныхразрядов, несколько счётчиковпо модулю2
8
A B (A B) (A B)
(( A B) ( A B))
9
Таблицаистинности |
A |
B |
C |
|
||
|
|
|
0 |
0 |
0 |
0 |
A |
B |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
|
|
1 |
1 |
0 |
0 |
|
|
|
1 |
1 |
1 |
1 |
В случае 2 переменных результатвыполнения операции является истинным тогдаи толькотогда,когдалишь один из аргументовявляется истинным.
Для функции 3и более переменных результатвыполнения операциибудет истинным толькотогда,когдаколичество аргументовравных 1, составляющих текущий набор –
нечетное.
10