Исторически теория кодирования появилась ближе к середине XX века. Конечно, она могла бы появиться гораздо раньше, потому что в каком-то смысле теория кодирования — это раздел комбинаторики, которой не счесть лет и историю которой можно вести от очень давних времен. Но тем не менее все-таки теория кодирования как отдельная дисциплина появилась ближе к середине XX века. Зато с тех пор она претерпела массу замечательных моментов и выросла до весьма глубокой и содержательной науки и как сама по себе исключительно красива, так и имеет массу содержательных приложений в самых разных технологиях.
Предмет теории кодирования очень прост. Вы хотите передавать информацию с помощью компьютера. Компьютер мыслит ноликами и единичками. Наиболее удобно передавать информацию, кодируя ее двоичным кодом. У вас есть какая-нибудь фраза, совершенно произвольная, — «Мама мыла раму» или «Над всей Испанией безоблачное небо», — и вы хотите ее передать. Заметьте, вы не хотите ее скрыть от внешнего наблюдателя, это же не шифрование. Ваша задача просто передать ее с помощью канала связи, который обеспечивает ваш компьютер, с помощью нулей и единиц. Ровно три слова: «Мама мыла раму».
Как это сделать? Можно каждому слову сопоставить некоторую последовательность из нулей и единиц. Скажем, «мама» — это 101, «мыла» — 010, «раму» — 001. А можно еще короче, ведь у нас всего три слова, по большому счету нам даже двух бит хватит, для того чтобы эту информацию передать. Потому что, когда у нас есть последовательность из двух циферок, даже если эти циферки только нуль и единица, у нас есть целых четыре таких последовательности: 00, 01, 10 и 11. А скажем, если у нас есть возможность для передачи чего-нибудь с помощью трех букв, вариантов становится восемь, 2*2*2. Если вы кодируете каждое слово последовательностью из k нулей и единиц, вы можете передать 2k различных последовательностей. Но на этом наука не заканчивается, конечно.
Дело в том, что, когда вы передаете информацию по каналу связи, иногда возникают помехи. Вы передаете «маму» с помощью 1-0-0, но из-за помех 1 может превратиться в 0, а 0 — в 1. Если известно, какое количество ошибок ожидать от данного канала связи, можно задаться вопросом: как вообще это сделать оптимальным образом? То есть, с одной стороны, добиться того, чтобы передавалось как можно больше различных, а с другой — гарантировать, что на выходе получится однозначно восстановить информацию.
Если рассуждать не в терминах нулей и единиц, а в терминах обычных слов, представьте передачу слов «мама» и «папа». Поскольку вы допускаете не более одной ошибки в каждом слове, то «мама» в «папу» никогда не превратится, зато может превратиться в «паму». А передавая «папу», вы, наоборот, можете одну из букв П испортить, заменив ее буквой М, — тоже получится «пама». Два слова склеились, и вы не можете на выходе восстановить информацию. Если слова изначально различались сильнее, как, скажем, «мама» и «крот», одна ошибка в каждом из этих слов не привела бы к разночтениям. «Пама» точно означала бы «маму», а какой-нибудь «куот» был бы кротом. Вы заранее знаете весь словарный запас и понимаете, что можно однозначно восстановить каждое слово.
Теория кодирования — это комбинаторная наука, которая позволяет строить такие оптимальные коды. Это совершенно нетривиальная задача. Понятно, что если вам нужно передавать очень длинные слова или последовательности из нулей и единиц, исправляя при этом даже фиксированное количество ошибок, то вам надо решить совершенно нетривиальную математическую задачу, которой занимаются десятилетиями и в которой еще масса нерешенных вопросов.
Можно сформулировать даже какую-нибудь нерешенную задачу, которая звучит безобидно, а в то же время никто не знает полного ответа на нее. Представьте себе, что вы передаете последовательности из десяти тысяч символов, каждый из которых может быть нулем или единицей. Вы хотите построить такой набор кодовых слов (кодовыми словами собственно называются последовательности из нулей и единиц), чтобы в каждом из этих кодовых слов было десять тысяч символов — пять тысяч единиц и пять тысяч нулей. И при этом хотите добиться того, чтобы каждые два кодовых слова имели бы ровно две с половиной тысячи общих единиц. Как много таких кодовых слов можно построить? Оказывается, это нерешенная проблема. Может быть, не для десяти тысяч, но для многих конкретных значений она не решена.
В связи с развитием современных технологий, компьютеров, больших данных, мощной вычислительной техники удается считать гораздо больше, чем удавалось пятьдесят или шестьдесят лет назад. Но комбинаторика — коварная наука. Сколько всего существует вообще последовательностей, у которых длина десять тысяч знаков? Никакие современные технологии не позволяют обрабатывать данные, объем которых не десять миллиардов или десять триллионов, а число, в котором три тысячи знаков. С комбинаторикой приходится бороться силами математики.
Теория кодирования легко борется с ситуациями, когда количество ошибок фиксировано, а размер передаваемой фразы растет к бесконечности. Если при передаче информации вы не услышали только две буквы из фразы, в которой десять тысяч символов, наверное, вы сможете восстановить информацию очень легко. Но задача становится тем труднее, чем ближе количество ошибок к количеству значимой информации. Если оно около половины, возникает проблема. Почему и важна наша нерешенная задача о кодах, исправляющих ошибки.
