Дисциплина Теория информации Тема №5: Помехоустойчивое кодирование

Министерство образования и науки РФ

Тамбовский государственный технический университет

Кафедра Информационные системы

 

Дисциплина Теория информации

Тема №5: Помехоустойчивое кодирование

Лекции №№ 9;10

специальность 230201 «Информационные системы и технологии»

3 курс

Преподаватель: проф. Дидрих Валерий Евгеньевич

Тамбов 2010

Тема №5: Помехоустойчивое кодирование

Классификация помехоустойчивых кодов.

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

По способу кодирования помехоустойчивые коды можно разделить на:

 

 

Блочное (блоковое) кодирование состоит в том, что каждой букве сообщения (или последовательности из k символов, соответствующей этой букве), ставится в соответствие блок из n символов. Причем n > k, а каждый символ блока формируется из k символов исходной последовательности по специально определенному правилу. На практике в блоке - от 3 до нескольких сотен символов.

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

Кодирование и декодирование непрерывных кодов носит непрерывный характер. При этом результат декодирования предыдущих и последующих символов может повлиять на декодирование текущего символа.

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

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

Разделимые коды условно обозначают в виде (n, k), где n-число символов в кодовой комбинации, k-число информационных символов. Тогда число проверочных символов в разделимых блоковых кодах равно: r=n-k.

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

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

 

Пример простейшего блокового разделимого систематического кода:

 

 

 

 

Алгоритм линейного систематического кодирования (5,4)

 

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

К несистематическим (нелинейным) кодам относятся коды, в которых проверочные символы формируются за счет нелинейных операций над информационными символами. Примером нелинейного кода является код Бергера.

 

 

Параметры (характеристики) помехоустойчивых кодов и их границы. Корректирующие свойства кодов.

- длина кода n; - основание кода m; - общее число кодовых комбинаций N;

Линейные (систематические) коды.

Механизмы кодирования и синдромного декодирования.

, где – множество информационных символов; – множество проверочных символов.