34

ВВЕДЕНИЕ

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

Практикум по курсу “Теория информации” составлен для студентов специальностей 2202 “Автоматизированные системы обработки информации и управления” и 0719 “Информационные системы (по отраслям применения)”.Цель его - ознакомление с общими методами формирования кодов, получение практических навыков по формированию корректирующих кодов на примере построения и декодирования кода Хемминга и систематического кода, изучение их свойств. Практикум состоит из двух частей ( первая посвящена методам построения кодов, а вторая - методам декодирования), иллюстрирован примерами, помогающими освоенить материал, снабжен таблицами, являющимися полезным справочным материалом.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

1. Кодирование информации. Основные понятия

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

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

Правила составления кодовых комбинаций (коды) и сами кодовые комбинации могут иметь различные характеристики: число кодовых признаков, используемых для комбинирования, количество разрядов кодовой комбинации, способ комбинирования (закон, согласно которому из единичных элементов образуются кодовые комбинации). Эти три свойства относятся к структурным характеристикам кода.

По числу кодовых признаков (символов) коды подразделяются на единичные, двоичные, многопозиционные. В единичном коде используется только один символ, и кодовые комбинации отличаются друг от друга лишь количеством символов. Кодовые комбинации двоичных кодов содержат два символа (0 или 1), многопозиционные - более двух.

По количеству разрядов кодовые комбинации разделяет коды на равномерные и неравномерные. Равномерные - это коды, все кодовые комбинации которых содержат постоянное количество разрядов; неравномерные содержат кодовые комбинации с различным числом разрядов. Неравномерные коды (избыточные) не нашли применения на практике из-за сложности их технической реализации.

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

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

2. Основные характеристики кодов

Оценка кодов обычно производится по их основным характеристикам, выражающим различные количественные и качественные показатели. Эти характеристики используются при выборе кодов, предназначенных для передачи, хранения и обработки информации: длина кода; основание кода; мощность кода; полное число кодовых комбинаций; число информационных символов; число проверочных символов; избыточность кода; скорость передачи; вес кодовой комбинации; кодовое расстояние d₀; весовая характеристика кода; вероятность необнаруженной ошибки; оптимальность кода; коэффициент ложных переходов.

Длина кода n - число разрядов (символов), составляющих кодовую комбинацию.

Основание кода m - количество отличающихся друг от друга значений импульсных признаков, используемых в кодовых комбинациях. Для случая двоичных кодов m=2. В качестве значений импульсных признаков используются цифры 0 и 1.

Мощность кода Np - число кодовых комбинаций (рабочих кодовых слов), используемых для передачи сообщений.

Полное число кодовых комбинаций N - это число всех возможных комбинаций, равное mⁿ(для двоичных кодов N =2ⁿ).

Число информационных символов (n_и) - количество символов (разрядов) кодовой комбинации, предназначенных для передачи сообщения. Очевидно:

N = (1)

Число проверочных символов (n_k) - количество символов (разрядов) кодовой комбинации, необходимых для коррекции ошибок. Это число характеризует абсолютную избыточность кода.

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

Скорость передачи кодовых комбинаций - отношение числа информационных символов к длине кода:

Поскольку n =n_k+n_и , то

R^’ = 1- R.

Пример. Определить избыточность и скорость передачи кода, предназначенного для передачи 16 сообщений, если длина двоичного кода n = 5. Полное число кодовых комбинаций:

N = 2ⁿ= 2⁵ = 32; тогда

R^’= 1-0.2=0,8

Вес кодовой комбинации (кода) w - количество единиц в кодовой комбинации. Например, кодовая комбинация 101100110 характеризуется длиной кода n =9 и весом w = 5.

Кодовое расстояние d₀ между комбинациями 10010111 и 00100110, необходимо просуммировать их по модулю два:

Полученная в результате суммированная новая кодовая комбинация характеризуется весом w = 4. Cледовательно, кодовое расстояние между исходными комбинациями d₀ = 4.

Весовая характеристика W (w)-число кодовых комбинаций веса w.

Пример. Для кода, содержащего кодовые комбинации 00000, 01110, 10101, 11011, весовая характеристика W(0)=1,W(3)=2,W(4)=1, т.е. код состоит из одного кодового слова, веса 0, двух слов веса 3 и одного слова веса 4.

ЛАБОРАТОРНАЯ РАБОТА 1