Мы живем в мире информации. Все, что мы видим, слышим, читаем, все, что мы знаем, помним, понимаем, все это информация. Информация может передаваться через речь, через различные средства связи (почта, электросеть, радио, телефон, телевидение и др.). Передаваемую информацию называют сообщением. Сообщения передаются при помощи сигналов. Сигнал называется дискретным, если он принадлежит некоторому конечному множеству сигналов (или, можно сказать, дискретный сигнал принимает конечное множество значений). Часто, дискретные сигналы называют знаками (знаками могут быть звуки языка, изображения, имеющие определенный смысл, жесты, обозначающие что-то). Сообщение называется дискретным, если оно может быть передано с помощью дискретных сигналов (знаков). Сообщения можно хранить на носителях информации (на бумаге, на дисках, на других носителях). Хранение информации можно считать долгосрочной передачей ее во времени. Знаки, из которых состоит хранимое сообщение, называют символами. А конкретное хранимое сообщение, состоящее из символов, называют записью.
Набор знаков (символов), используемый для конкретного хранения или передачи информации, в котором определен линейный порядок знаков, называется алфавитом.
Символы алфавита иногда называют буквами. Наборы символов (букв) конкретного алфавита называют словами. Например, пусть задан алфавит A = {a,b,c}, тогда baabaca является словом над алфавитом A. Пусть теперь A - произвольный конечный алфавит, обозначим через A*множество всех слов над алфавитом A. Естественно, множество A* бесконечно. Обозначим через A+ произвольное конечное подмножество множества A*.
Пусть S = {s1,s2, …, sn} - некоторое произвольное конечное множество (например, множество конкретных информационных объектов, например, сообщений). Пусть задана функция F, отображающая множество S в множество слов A+ над алфавитом A, то есть F: S → A+. Такая функция F называется кодированием элементов множества S в слова над алфавитом A. Если элемент s множества S при кодировании F отобразился, например, в слово baabacaнад алфавитом A, то будем писать F: s → baabaca, или F(s)= baabaca.
Правило, описывающее отображение F называется кодом. Кодом также называют и множество образов при этом отображении. Кодом конкретного элемента s будем называть слово F(s). Так как S и A+ конечные множества, то функцию F можно описать таблично:
s1 → A1
s2 → A2
…………
sn → An
где A1, A2, … An - некоторые слова над алфавитом A.
Это табличное описание кодирования F и будет его кодом. Кодом в этом случае будем называть и сам набор слов (A1, A2, … An),а сами эти слова будем называть кодовыми словами. Если алфавит A состоит всего из двух букв (то есть │A│= 2), то соответствующее кодирование F называется двоичным кодированием. Обычно в этом случае буквы алфавита A обозначаются цифрами 0 и 1. Кодовыми словами при таком кодировании будут наборы из 0 и 1.
Получаемая при кодировании последовательность кодовых слов, которые обычно записываются подряд без разделения пробелом или специальным разделяющим символом (то есть слитная запись последовательности), называется кодовой последовательностью. Разделяющие символы, если они применяются при кодировании (как например, в азбуке Морзе, см. ниже), считаются обычными символами алфавита A (алфавита кодовых слов) и должны присоединяться к кодовым словам, а сама кодовая последовательность рассматривается как непрерывная последовательность символов.
Обратное преобразование по отношению к F называется декодированием, и обозначается F-1. Чтобы декодирование было однозначным, необходимо, чтобы
│S │= n ≤ │A+│ и все кодовые слова были различны. Обозначим множество всех кодовых слов K, тогда существование взаимно-однозначного соответствия между S и K, определяемого функцией F (F: S↔K, │K│= n), является необходимым условием однозначности декодирования, но, к сожалению, оно не является достаточным. Как мы далее узнаем, проблемы при декодировании могут возникать, когда кодовую последовательность приходится разбивать на кодовые слова. Такое разбиение кодовой последовательности не всегда однозначно.
Иногда кодирование называют шифрованием, а декодирование – дешифрованием, соответственно, код называют шифром. Такая терминология в основном используется в криптографии, где изучаются методы кодирования секретной, конфиденциальной информации, которые обеспечивают невозможность расшифровки без знания шифра.
Пусть теперь S - некоторый алфавит, для букв которого определено кодирование F в слова над алфавитом A. Тогда можно говорить о кодировании слов над алфавитом S при помощи функции F. Такое кодирование называется алфавитным (или побуквенным). Функция F распространяется на слова над S следующим образом: кодом слова X при кодировании F будет слитное написание кодов каждой буквы слова X. Например, пусть X = abcd, тогда F(X)=F(a)F(b)F(c)F(d) , где справа стоит кодовая последовательность, полученная кодированием слова X, и состоит из букв кодов каждой буквы X, записанных подряд.
