Рождение теории кодирования

«Открытые системы»

Создание компьютеров было бы невозможно, если одновременно с их появлением не была бы создана теория кодирования сигналов

Теория кодирования — одна из тех областей математики, которые заметно повлияли на развитие компьютинга. Ее область действия распространяется на передачу данных по реальным (или зашумленным) каналам, а предметом является обеспечение корректности переданной информации. Иными словами, она изучает, как лучше упаковать данные, чтобы после передачи сигнала из данных можно было надежно и просто выделить полезную информацию. Иногда теорию кодирования путают с шифрованием, но это неверно: криптография решает обратную задачу, ее цель — затруднить получение информации из данных.

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

С необходимостью кодирования данных впервые столкнулись более полутораста лет назад, вскоре после изобретения телеграфа. Каналы были дороги и ненадежны, что сделало актуальной задачу минимизации стоимости и повышения надежности передачи телеграмм. Проблема еще более обострилась в связи с прокладкой трансатлантических кабелей. С 1845 года вошли в употребление специальные кодовые книги; с их помощью телеграфисты вручную выполняли «компрессию» сообщений, заменяя распространенные последовательности слов более короткими кодами. Тогда же для проверки правильности передачи стали использовать контроль четности, метод, который применялся для проверки правильности ввода перфокарт еще и в компьютерах первого и второго поколений. Для этого во вводимую колоду последней вкладывали специально подготовленную карту с контрольной суммой. Если устройство ввода было не слишком надежным (или колода — слишком большой), то могла возникнуть ошибка. Чтобы исправить ее, процедуру ввода повторяли до тех пор, пока подсчитанная контрольная сумма не совпадала с суммой, сохраненной на карте. Мало того, что эта схема неудобна, она к тому же пропускает двойные ошибки. С развитием каналов связи потребовался более эффективный механизм контроля.

Первым теоретическое решение проблемы передачи данных по зашумленным каналам предложил Клод Шеннон, основоположник статистической теории информации. Шеннон был звездой своего времени, он входил в академическую элиту США. Будучи аспирантом Ванневара Буша, в 1940 году он получил премию имени Нобеля (не путать с Нобелевской премией!), присуждаемую ученым, не достигшим 30 лет. Работая в Bell Labs, Шеннон написал работу «Математическая теория передачи сообщений» (1948), где показал, что если пропускная способность канала выше энтропии источника сообщений, то сообщение можно закодировать так, что оно будет передано без излишних задержек. Это умозаключение содержится в одной из доказанных Шенноном теорем, ее смысл сводится к тому, что при наличии канала с достаточной пропускной способностью сообщение может быть передано с некоторыми временными задержками. Кроме того, он показал теоретическую возможность достоверной передачи при наличии шума в канале. Формулу C = W log ((P+N)/N), высеченную на скромном памятнике Шеннону, установленном в его родном городе в штате Мичиган, сравнивают по значению с формулой Альберта Эйнштейна E = mc².

Труды Шеннона дали пищу для множества дальнейших исследований в области теории информации, но практического инженерного приложения они не имели. Переход от теории к практике стал возможен благодаря усилиям Ричарда Хэмминга, коллеги Шеннона по Bell Labs, получившего известность за открытие класса кодов, которые так и стали называть «кодами Хэмминга». Существует легенда, что к изобретению своих кодов Хэмминга подтолкнуло неудобство в работе с перфокартами на релейной счетной машине Bell Model V в середине 40-х годов. Ему давали время для работы на машине в выходные дни, когда не было операторов, и ему самому приходилось возиться с вводом. Как бы то ни было, но Хэмминг предложил коды, способные корректировать ошибки в каналах связи, в том числе и в магистралях передачи данных в компьютерах, прежде всего между процессором и памятью. Коды Хэмминга стали свидетельством того, как можно практически реализовать возможности, на которые указывают теоремы Шеннона.

Хэмминг опубликовал свою статью в 1950 году, хотя во внутренних отчетах его теория кодирования датируется 1947 годом. Поэтому некоторые считают, что отцом теории кодирования следует считать Хэмминга, а не Шеннона. Впрочем, в истории техники бесполезно искать первого.

Достоверно только то, что именно Хэмминг первым предложил «коды с исправлением ошибок» (Error-Correcting Code, ECC). Современные модификации этих кодов используются во всех системах хранения данных и для обмена между процессором и оперативной памятью. Один из их вариантов, коды Рида-Соломона применяются в компакт-дисках, позволяя воспроизводить записи без скрипов и шумов, которые могли бы вызвать царапины и пылинки. Существует множество версий кодов, построенных «по мотивам» Хэмминга, они различаются алгоритмами кодирования и количеством проверочных битов. Особое значение подобные коды приобрели в связи с развитием дальней космической связи с межпланетными станциями, например, существуют коды Рида-Мюллера, где на семь информационных битов приходится 32 контрольных, или на шесть — 26.

Среди новейших кодов ECC следует назвать коды LDPC (Low-Density Parity-check Code). Вообще-то они известны лет тридцать, но особый интерес к ним обнаружился именно в последние годы, когда стало развиваться телевидение высокой четкости. Коды LDPC не обладают 100-процентной достоверностью, но вероятность ошибки может быть доведена до желаемой, и при этом с максимальной полнотой используется пропускная способность канала. К ним близки «турбокоды» (Turbo Code), они эффективны при работе с объектами, находящимися в условиях далекого космоса и ограниченной пропускной способности канала.

В историю теории кодирования прочно вписано имя Владимира Александровича Котельникова. В 1933 году в «Материалах по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи» он опубликовал работу «О пропускной способности ‘эфира’ и ‘проволоки’». Имя Котельникова на правах равного входит в название одной из важнейших теорем теории кодирования. Этой теоремой определяются условия, при которых переданный сигнал может быть восстановлен без потери информации.

Эту теорему называют по-разному, в том числе «теоремой WKS» (аббревиатура WKS взята от Whittaker, Kotelnikov, Shannon). В некоторых источниках используют и Nyquist-Shannon sampling theorem, и Whittaker-Shannon sampling theorem, а в отечественных вузовских учебниках чаще всего встречается просто «теорема Котельникова». На самом же деле теорема имеет более долгую историю. Ее первую часть в 1897 году доказал французский математик Эмиль Борель. Свой вклад в 1915 году внес Эдмунд Уиттекер. В 1920 году японец Кинносуки Огура опубликовал поправки к исследованиям Уиттекера, а в 1928 году американец Гарри Найквист уточнил принципы оцифровки и восстановления аналогового сигнала.

Клод Шеннон (1916 — 2001) со школьных лет проявлял равный интерес к математике и электротехнике. В 1932 году он поступил в Университет штата Мичиган, в 1936-м — в Массачусетский технологический институт, который закончил в 1940 году, получив две степени — магистра по электротехнике и доктора в области математики. В 1941 году Шеннон поступил на работу в Bell Laboratories. Здесь он начал развивать идеи, которые впоследствии вылились в теорию информации. В 1948-м Шеннон опубликовал статью «Математическая теория связи», где были сформулированы базовые идеи ученого, в частности, определение количества информации через энтропию, а также предложил единицу информации, определяющую выбор из двух равновероятных вариантов, то есть то, что впоследствии назвали битом. В 1957-1961 годах Шеннон опубликовал работы, где доказывалась теорема о пропускной способности зашумленных каналов связи, которая теперь носит его имя. В 1957 году Шеннон стал профессором Массачусетского технологического института, откуда ушел на пенсию спустя 21 год. На «заслуженном отдыхе» Шеннон полностью отдался своему давнему увлечению жонглированием. Он построил несколько жонглирующих машин и даже создал общую теорию жонглирования.

Ричард Хэмминг (1915 — 1998) начал свое образование в Чикагском университете, где в 1937 году получил степень бакалавра. В 1939 году он получил степень магистра в Университете Небраски, а степень доктора по математике — в Университете Иллинойса. В 1945 году Хэмминг начал работать в рамках Манхэттенского проекта — масштабной государственной научно-исследовательской работы по созданию атомной бомбы. В 1946 году Хэмминг поступил на работу в Bell Telephone Laboratories, где работал в том числе с Клодом Шенноном. В 1976 году Хэмминг получил кафедру в военно-морской аспирантуре в Монтерей в Калифорнии.

Труд, сделавший его знаменитым, фундаментальное исследование кодов обнаружения и исправления ошибок, Хэмминг опубликовал в 1950 году. В 1956 году он принимал участие в работе над одним из ранних мэйнфреймов IBM 650. Его работы заложили основу языка программирования, который позднее эволюционировал в языки программирования высокого уровня. В знак признания заслуг Хэмминга в области информатики институт IEEE учредил медаль за выдающиеся заслуги в развитии информатики и теории систем, которую назвал его именем.

Владимир Котельников (1908 — 2005) в 1926 году поступил на Электротехнический факультет Московского высшего технического училища имени Н. Э. Баумана (МВТУ), но стал выпускником Московского энергетического института (МЭИ), который выделился из МВТУ как самостоятельный институт. Во время обучения в аспирантуре (1931-1933) Котельников математически точно сформулировал и доказал «теорему отсчетов», которая впоследствии была названа его именем. После окончания аспирантуры в 1933 году Котельников, оставаясь преподавать в МЭИ, поступил на работу в Центральный научно-исследовательский институт связи (ЦНИИС). В 1941 году В. А. Котельников сформулировал четкое положение о том, каким требованиям должна удовлетворять математически недешифруемая система и дано доказательство невозможности ее дешифровки. В 1944 году Котельников занял должность профессора, декана радиотехнического факультета МЭИ, где проработал до 1980 года. В 1953 году в возрасте 45 лет Котельников был избран сразу действительным членом Академии наук СССР. С 1968 по 1990 год В. А. Котельников был также профессором, заведующим кафедрой Московского физико-технического института.