Теория кодирования. Кодирование: история и первый шаг

Теория кодирования. Кодирование: история и первый шаг.

Теория кодирования-одна из областей математики, которая внесла свой вклад в развитие компьютеризации. Область ее распространения-передача данных по конкретным каналам, а ее предмет-обеспечение достоверности передаваемой информации. Некоторые путают теорию кодирования с шифрованием, но это неверно: криптография решает обратную задачу, цель которой состоит в том, чтобы затруднить извлечение информации из данных.

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

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

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

Мы знаем, что Хемминг был первым, кто предложил «Коды исправления ошибок» (Error-Correcting Code, ECC). Известно, что современные модификации этих кодов используются во всех системах хранения информации и для обмена между памятью и процессором. Один из их вариантов код Рида-Соломона используется на компакт-дисках. Существует множество вариантов кода, разработанных по методу Хэмминга, которые различаются по алгоритмам кодирования и по количеству проверяемых битов. Особое внимание стало уделяться таким кодам для космической связи с межпланетными станциями, например, коды Рида-Мюллера поступали в 7 информационных битах по 32 проверочных бита или в 6 информационных битах – по 26 проверочных бита. В качестве одного из новых кодов ECC мы можем назвать код LDPC (Low-Density Parity-Check Code). В принципе, они были популярны лет тридцать назад, но в настоящее время им уделяется особое внимание. Хотя код LDPC имеет 100-процентную четкость, он позволяет нам довести вероятность ошибки до желаемого результата и при этом максимально полно используется возможность отправки канала. К ним очень близко подходят «турбокоды» (Turbo Code), которые идеально подходят при работе с объектами в далеком космосе.

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

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