Надёжность передачи и хранения информации. Вторая теорема Шеннона.

Надежной или достоверной считается такая передача или хранение информации, при которой не происходит её искажение, отсутствуют её потери.

Вторая теорема К. Шеннона

При передаче информации по каналу с шумами всегда можно выбрать способ кодирования, при котором сообщение передается со сколь угодно высокой достоверностью, если скорость передачи не превышает пропускной способности канала.

Надежность передачи сообщения обеспечивается тем, что кроме информационных бит сообщение содержит дополнительные - контрольные биты, по состоянию которых можно судить о правильности передачи.

Пусть ki - количество информационных битов, kc - количество контрольных битов, k = ki+kc. Относительная избыточность сообщения L для реального канала равна:

 

Кодирование с обнаружением и исправлением ошибок.

Существуют способы кодирования, позволяющие установить факт появления ошибки - обнаружение ошибки, и способы, обеспечивающие и обнаружение и исправление ошибок.

 

Обнаружение ошибки

Общепринятый способ, обеспечивающий обнаружение одиночной ошибки. В каждый байт включается один контрольный разряд, с помощью которого проводится проверка на нечетность по правилу: количество единиц в байте (включая контрольный разряд) должно быть нечетным.

Обнаружение одиночной ошибки с помощью контрольного бита.
Относительная избыточность равна:

 

Коды с исправлением ошибок - коды Хемминга.

Тройка битов снабжается одним контрольным разрядом. Количество единиц в каждой области должно быть нечетным. Для 4 информационных битов достаточно выделение контрольных разрядов для 3 из возможных 4 троек.

Ошибочный бит находится в секторе общем для областей с нарушенной четностью.

Коды Хемминга.

Принцип построения кодов Р. Хемминга (1948 г.).

1. Контрольные биты включаются в исходный код и нумеруются совместно с информационными битами слева направо, начиная с 1.

2. Контрольные биты располагаются в позициях с номерами n=2 , k=0,1,2,3 ,…;

3. Для каждого контрольного разряда с номером n весь код делится на группы, состоящие из 2хn битов.

4. Контрольный бит с номером n контролирует в группе первые n подряд расположенных битов кода (для первой группы включая контрольный) с пропуском следующих n битов.

 

В общем случае информационный бит с номером b проверяется контрольными битами с номерами , такими, что

Количество битовых позиций, в которых два кода отличаются друг от друга называется интервалом Хемминга двух кодов.

Для всех возможных m битовых кодов и r контрольных битов существует минимальный интервал, который называется интервалом Хемминга полного кода.

Допустимым считается код, у которого правильно заданы значения контрольных разрядов.

Для обнаружения k ошибок, необходим код с полным интервалом d=k+1, а для исправления k ошибок, необходим код с полным интервалом d=2k+1.

 

Разрядность кодов Хемминга для исправления одиночных ошибок

Для заданного допустимого кода разрядности m существует ровно n=m+r кодов с единственной ошибкой и n+1 кодов с не более чем одной ошибкой. Всего допустимых кодов . Всего кодов с не более чем одной ошибкой 2m(n+1). Должно выполняться неравенство

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: