Глава 1. История кодирования

Введение

Коды возникли в глубокой древности, фактически с появлением системы знаков для записи звуков, слов, и информации, которые позднее развились в различные языки. Каждый язык представляет собой сложную систему кодирования, включая в свою конструкцию алфавит, слова, грамматику. Язык позволяет передавать в окружающем шуме информацию быстро, надежно и с достаточной степенью избыточности. В течении многих веков люди занимались засекречиванием информации и созданием кодов. Впоследствии была разработана теория кодирования, являющаяся одним из разделов теоретической информатики. Быстрый рост объемов обработки данных, развитие вычислительных сетей предъявляют высокие требования к минимизации ошибок в используемой информации. Переход всех видов создания, хранения, использования и передачи данных, а также средств вещания на цифровые методы, происходящий сейчас во всём мире, ещё более повышает важность высококачественной передачи цифровых потоков. Успешная работа этих систем возможна только при наличии специальной эффективной аппаратуры, которая позволяет гарантировать достоверную передачу информации. Важнейший вклад в повышение достоверности обмена цифровыми данными вносит теория кодирования.

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

Глава 1. История кодирования

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

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

Не нашли, что искали? Воспользуйтесь поиском: