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

При математическом анализе систем связи обычно пользуются упрощенными моделями. Для двоичного алфавита {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.

Дата добавления: 2015-08-03