Дискретная информация записывается и передается с помощью некоторого конечного набора знаков, которые будем называть буквами, не вкладывая в это слово привычного ограниченного значения. В расширенном понимании буква – любой из знаков, которые некоторым соглашением установлены для общения. Множество букв, в котором определен их порядок, называется алфавит.
Примеры алфавитов:
1. Алфавит прописных русских букв: А Б ... Я
2. Алфавит клавиатурных символов ЭВМ;
3. Алфавит арабских цифр: 0 1 2 3 4 5 6 7 8 9;
4. Алфавит шестнадцатиричных цифр: 0 1 2 3 4 5 6 7 8 9 A B C D E F;
5. Алфавит двоичных цифр: 0 1.
Буквы одного алфавита могут состоять также и в других алфавитах, причем не обязательно на том же месте, и могут нести различный смысл (пример 4: буквы несут числовое значение).
Сообщение, составленное из букв одного алфавита (кодируемого), может преобразовываться в сообщение из букв другого алфавита (кодирующего). Правило, описывающее однозначное соответствие букв алфавитов при таком преобразовании, называют кодом. Подобное преобразование сообщения может осуществляться, например, в момент поступления сообщения от источника в канал связи (кодирование) и в момент приема сообщения получателем (декодирование). Устройства, обеспечивающие кодирование и декодирование, называются (с точки зрения математики) кодировщиком и декодировщиком.
Примеры кодов:
1) Азбука Морзе: алфавиту, составленному из букв и арабских цифр ставится в соответствие алфавит Морзе (. и -);
2) Код Трисиме: знакам латинского алфавита ставятся в соответствие комбинации из трех знаков (0,1,2):
A 000 B 001 C 002 D 010 E 011 F 012 G 020 H 021 I 022 J 100 K 101 L 102 M 110 N 111 O 112 P 120 Q 121 R 122 S 200 T 201 U 202 V 210 W 211 X 212 Y 220 Z 221 пробел 222
Последний код (Трисиме) является примером так называемого равномерного кода, т.е. такого, в котором все кодовые комбинации для букв кодируемого алфавита содержат одинаковое число знаков кодирующего алфавита. Равномерное кодирование с точки зрения информатики имеет несомненные преимущества перед неравномерным, поэтому все компьютерные системы используют равномерные коды.
Коды могут быть прямыми и сложными.
Прямой код – когда исходное сообщение может быть разбито на фрагменты определенной длины (т.е. на группы из определенного числа букв), которые кодируются независимо от остальной части сообщения, причем одинаковым группам букв соответствуют одинаковые кодовые комбинации. Если же такого сделать нельзя, то код называют сложным.
Пример прямого кода – перевод чисел из двоичной системы счисления в восьмеричную и обратно: исходное сообщение (двоичный код) разбивается на группы по три буквы, и каждой группе ставиться в соответствии одна буква восьмеричного алфавита. Сложный код – перевод чисел из десятичной системы счисления в двоичную: число переводится целиком и его нельзя разбить на фрагменты. Прямое кодирование осуществляется намного легче, чем сложное, но, с другой стороны, сложные коды предоставляют больше возможностей по защите информации.
Помехоустойчивое кодирование
При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых сигналов. Проблема передачи сообщений при наличии помех является серьезной теоретической и практической задачей. Ее значимость возрастает в связи с повсеместным внедрением компьютерных телекоммуникаций, в которых помехи неизбежны. При работе с кодированной информацией, искажаемой помехами, можно выделить следующие основные проблемы: установление самого факта того, что произошло искажение информации; выяснения того, в каком конкретно месте передаваемого сообщения это произошло; исправления ошибки, хотя бы с некоторой степенью достоверности.
Помехи в передаче информации – обычное дело во всех сферах человеческой деятельности и в быту. Например, разговор по телефону с помехами, нечеткий сигнал с телевизионной антенны, вождение автомобиля в тумане и т.п. Чаще всего человек вполне справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет в том, как именно он это делает (чаще всего это происходит не алгоритмически, а исходя из каких-то ассоциативных связей). Но с точки зрения информатики требуются четкие математические принципы эффективного помехоустойчивого кодирования.
Впервые теоретическое исследование этой проблемы предпринял К. Шеннон. Две доказанные им теоремы декларируют возможность создания системы эффективного помехоустойчивого кодирования в рамках одного алфавита, если пропускная способность канала связи превышает производительность источника сообщений. Теоремы Шеннона не дают конкретного метода построения кода, но указывают на пределы достижимого в создании помехоустойчивых кодов, стимулируют поиск новых решений в этой области.
Для двоичного кода одним из способов помехоустойчивого кодирования может служить троекратное повторение каждого бита (т. е. ...10011... кодируется как ...111000000111111...), а при декодировании полученный код разбивается на триады, и каждая триада заменяется одним символом, который присутствует в ней по меньшей мере в двух позициях. (т.е. ...000 110 010 110 111 101 110... = ...0101111...). Такая система не будет полностью помехоустойчивой, но позволяет защититься от одиночных искажений. Так, если после каждого искаженного символа следует минимум два неискаженных, то такая система будет полностью помехоустойчивой. Однако, для реализации подобного метода кодирования необходимо, чтобы пропускная способность канала минимум втрое превышала производительность источника сообщений (код обладает тройной избыточностью), что бывает далеко не всегда. Вообще, построение помехоустойчивых кодов с малой избыточностью – сложная математическая задача, которая полностью не решена до сих пор.
