Двоичные симметричные каналы

Наша основная цель – знакомство с методами построения эффективных схем кодирования информации для передачи по реальным каналам с «шумами».

Информационное сообщение всегда связано с источником информации, приемником информации и каналом передачи.

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

Источник информации		Канал связи		Приемник информации

Рис.1 Информационная модель канала связи

Чтобы передать информацию, её необходимо предварительно преобразовать.

Кодирование – это преобразование сообщения в форму, удобную для передачи по каналу связи.

Пример: передача сообщения в виде телеграммы. Все символы кодируются с помощью телеграфного кода.

Декодирование – операция восстановления принятого сообщения.

В систему связи необходимо ввести устройства для кодирования и декодирования информации.

Источник информации		Кодер		Декодер		Получатель (приемник)
	Канал
	| | |

Помехи

Рис.2. Процесс передачи сообщения от источника к приемнику (получателю)

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

1. обнаружить ошибки, если они возникают;

2. исправлять найденные ошибки;

3. защищать информацию, передающуюся по каналам связи;

4. ускорять передачу информации по каналу связи.

Из перечисленных проблем теория кодирования исследует первую и вторую. Третьей проблемой занимается криптография.[2] Четвертая же является прикладной для криптографии и теории кодирования как параметр, с помощью которого определяется качество криптографии и кодирования.

Пусть мы хотим передать сообщение, которое может быть строкой символов некоторого конечного алфавита: {0,1}, или {строчные и/или прописные латинские буквы}, или {арабские цифры} и т.п.

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

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

Таким образом, передача данных сводится к передаче по некоторому каналу связи знаков некоторого конечного алфавита. Практически всегда канал связи не идеален.

Двоичные симметричные каналы

При математическом анализе систем связи обычно пользуются упрощенными моделями. Для двоичного алфавита {0,1} простейшая достаточно реалистическая модель называется двоичным симметрическим каналом. Пусть двоичные сигналы 0,1 последовательно передаются по каналу связи на приемник.

На рис.3 представлена ситуация, когда каждый символ принимается правильно с вероятностью р и ошибочно с вероятностью q = 1- p.

Рис. 3 Вероятность перехода в двоичном симметричном канале.

Идея, положенная в основу использования любого систематического кода такова: сообщение, подлежащее передаче, кодируется по определенной схеме более длинной последовательностью символов в алфавите {0, 1}. Эта последовательность называется кодом [3] или кодовым словом. При приеме можно исправлять или распознавать ошибки, возникшие при передаче по каналу связи, анализируя информацию, содержащуюся в дополнительных символах.

Систематический код – код, содержащий в себе кроме информационных контрольные разряды.

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

Двоичным (m, n)–кодом называется пара, состоящая из схемы кодирования E:2^m®2ⁿ и схемы декодирования D:2ⁿ®2^m, где 2ⁿ – множество двоичных последовательностей длины n.

Все помехоустойчивые коды делятся на два больших класса:

· коды с обнаружением ошибок, которые имеет целью только выяснить наличие ошибок.

· коды с исправлением ошибок, которые имеют целью восстановить посланное сообщение, если при передаче его исказили.

Для иллюстрации приведем два примера.

Пример реализации метода четности представлен в таблице.

		Таблица 1
Число	Контрольный разряд	Проверка
		1 – нарушение

Контроль по методу четности широко используют в ЭВМ для контроля записи, считывания информации в запоминающих устройствах на магнитных носителях, а также при выполнении арифметических операций.

Теперь подробнее разберем пример кода с исправлением ошибок. Простейший пример такого кодирования состоит в повторении сигнала, хотя этот способ далек от оптимального.

При декодировании решение принимается «большинством голосов», т.е. переданным считается символ, встречающийся большее число раз. При больших r мы практически обезопасим себя от ошибок, однако передача сообщений будет идти очень медленно.

Описанные примеры принадлежат к классу блочных кодов, т.е. блочный код заменяет каждый блок из m символов некоторым более длинным блоком из n символов (m n), который после передачи подлежит декодированию.

Блочный код обозначается (m, n) - код.

Случай m=n используется в шифровании, где цель кодирования состоит в обеспечении секретности сигнала.

В математической модели кодирования и декодирования удобно рассматривать строки ошибок. Данное сообщение а = а₁ а₂ … а_m кодируется кодовым словом в = в₁, в₂, …, в_n. При передаче канал связи добавляет к нему строку ошибок ℓ = ℓ₁ ℓ₂, … ℓ_n, так что приемник принимает сигнал с = с₁ с₂ …с_n, где с_i = в_i + ℓ_i.

Система, исправляющая ошибки, переводит слово с₁ с₂ …с_n в ближайшее кодовое слово в₁, в₂, …, в_n.

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

Пусть, например, передаваемое слово а = 01 кодируется словом в= 0110, а строка ошибок есть ℓ = 0010. Тогда будет принято слово с = 0100. Система, исправляющая ошибки, переведет его в 0100 и затем восстановит переданное слово 01.