История развития кодирования до наших дней

Индивидуальное задание

по  дисциплине «Дискретная  математика»

тема: «История развития кодирования до наших дней» 
 
 
 
 
 
 
 
 

                                            выполнил:

                                            группа:  
 
 
 

Москва, 2011 

     Введение

     Необходимость кодирования информации возникла задолго  до появления компьютеров. Речь, азбука и цифры – есть не что иное, как система моделирования мыслей, речевых звуков и числовой информации. В технике потребность кодирования  возникла сразу после создания телеграфа, но особенно важной она стала с  изобретением компьютеров.

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

     В данной работе мы рассмотрим основные этапы развития кодирования до наших  дней.

     История развития кодирования

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

     Первым  теоретическое решение проблемы передачи данных по зашумленным каналам  предложил Клод Шеннон, основоположник статистической теории информации. Работая  в Bell Labs, Шеннон написал работу «Математическая теория передачи сообщений» (1948), где показал, что если пропускная способность канала выше энтропии источника сообщений, то сообщение можно закодировать так, что оно будет передано без излишних задержек. В одной из теорем Шеннон доказал, что при наличии канала с достаточной пропускной способностью сообщение может быть передано с некоторыми временными задержками. Кроме того, он показал возможность достоверной передачи при наличии шума в канале.

     Формула C = W log ((P+N)/N), высечена на скромном памятнике Шеннону, установленном в его родном городе в штате Мичиган.

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

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

     Ричард  Хэмминг (1915 - 1998) получил степень  бакалавра в Чикагском университете в 1937. В 1939 он получил степень магистра в Университете Небраски, а степень  доктора по математике – в Университете Иллинойса. В 1945 Хэмминг начал работать в рамках Манхэттенского проекта. В1946 поступил на работу в Bell Telephone Laboratories, где работал с Шенноном. В 1976 получил кафедру в военно-морской аспирантуре в Монтерей в Калифорнии. Труд, сделавший его знаменитым, фундаментальное исследование кодов обнаружения и исправления ошибок, Хэмминг опубликовал в 1950. В 1956 он принимал участие в работе над IBM 650. Его работы заложили основу языка программирования, который позднее эволюционировал в языки программирования высокого уровня. В знак признания заслуг Хэмминга в области информатики институт IEEE учредил медаль за выдающиеся заслуги в развитии информатики и теории систем, которую назвал его именем. Хэмминг первым предложил «коды с исправлением ошибок» (Error-Correcting Code, ECC).

     Современные модификации этих кодов используются во всех системах хранения данных и  для обмена между процессором  и оперативной памятью. Один из их вариантов, коды Рида-Соломона применяются  в компакт-дисках, позволяя воспроизводить записи без скрипов и шумов, вызванных  царапинами и пылинками. Существует множество версий кодов, построенных  «по мотивам» Хэмминга, они различаются  алгоритмами кодирования и количеством  проверочных битов. Особое значение подобные коды приобрели в связи  с развитием дальней космической  связи с межпланетными станциями.

     Среди новейших кодов 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 американец Гарри Найквист уточнил принципы оцифровки и восстановления аналогового сигнала.

     Работа  Хэмминга явилась катализатором  цепной реакции выдвижения новых идей в истории кодирования, которая началась с 1954 года. Американский ученый И. С. Рид был первым, кто использовал мажоритарное декодирование кодов Рида-Маллера. При мажоритарном декодировании для каждого информационного символа формируется нечетное число оценок путем сложения по модулю 2 определенных комбинаций символов принятого кода. Решение об истинном значении принятого символа принимается по мажоритарному принципу - если большее количество оценок равно 1, то принимается именно такое решение. В 1963 году Дж. Л. Месси установил общие принципы построения и декодирования подобных кодов. Достоинством мажоритарно декодируемых кодов является чрезвычайная простота и быстродействие алгоритмов декодирования. Однако класс таких кодов весьма мал, и эти коды слабее других. Значительный вклад в создание теории построения мажоритарно декодируемых кодов внесли в 1965 году советские ученые В. Д. Колесников и Е. Т. Мирончиков.

     Весьма  интересный класс блочных кодов  был предложен в 1954 году американским ученым Г. Форни. Каскадные коды формируются следующим образом: последовательность информационных символов длиной n = n1 * n2 записывается в буферную память в виде таблицы, имеющей n1 столбцов и n2 строк. Символы отдельных строк и столбцов кодируются с помощью корректирующих кодов (соответственно внутреннего и внешнего), и дополнительные проверочные символы вместе с информационными передаются по каналу связи. Весьма значимые результаты по исследованию каскадных кодов были получены Г. Форни и советскими учеными Э. Л. Блохом и В. В. Зябловым. Исследования последних (1976 и 1982 гг.) показали, что при соответствующем выборе внутреннего и внешнего кодов каскадные коды позволяют разрешить указанные выше проблемы помехоустойчивого кодирования.

     В 1955 году в США и СССР был предложен  весьма важный класс сверточных или рекуррентных кодов, нашедший широкое применение в современной технике связи. Исследования, связанные с построением таких кодов и разработкой эффективных с вычислительной точки зрения алгоритмов их декодирования, заняли почти двадцать лет. В этом классе кодов информационная последовательность символов разбивается на блоки, содержащие по m символов, которые поступают на линейный преобразователь, имеющий память на K-подобных блоков. В этом преобразователе каждый блок из m поступивших символов с учетом содержащихся в памяти K-блоков (K - длина кодового ограничения), преобразуются в n (n > m) символов, передаваемых по каналу связи. При этом относительная скорость передачи информации составляет R = m/п. Сверточные коды являются частным случаем блочных линейных кодов. Однако введение сверточной структуры наделяет эти коды рядом дополнительных свойств, которые существенно облегчают его декодирование. Эти коды имеют древовидную или решетчатую структуру. Каждому ребру древовидной структуры соответствует определенная последовательность m информационных символов. По принятой последовательности символов для каждого ребра может быть найден его вес - число, характеризующее его расстояние от принятой последовательности. Для измерения этого расстояния может быть использована метрика Хэмминга, если в демодуляторе принимается жесткое решение, или евклидова метрика, если декодирование осуществляется по методу максимума правдоподобия. Декодирование сверточных кодов состоит в прослеживании по кодовой решетке того пути, для которого расстояние от принятой последовательности символов имеет минимальное значение. Сверточная структура кода позволяет использовать рекуррентные алгоритмы, существенно упрощающие вычисления этого расстояния.

     Для декодирования этих кодов американским ученым Дж. Возенкрафтом в 1957 году был предложен изящный алгоритм последовательного декодирования, в соответствии с которым в декодере просматриваются не все возможные пути по ребрам кодовой решетки сверточного кода, а наиболее вероятные. Если декодер выбрал на каком-то шаге неверный путь, то он вскоре обнаруживает, что при последующих выборах ребер происходит быстрое увеличение расстояния между выбранным путем и принимаемой последовательностью. Это является сигналом к тому, чтобы декодер сделал несколько шагов назад и начал исследовать альтернативные, более правдоподобные пути. При последовательном декодировании число вычислений на одно ребро является случайной величиной, и в памяти декодера должны храниться вычисленные расстояния для всех исследованных ветвей. Первые исследования алгоритма последовательного декодирования выполнили Дж. Возенкрафт и Б. Рейффен. В 1963 году его усовершенствовал P. M. Фано, в 1966 году эффективную модификацию этого алгоритма предложил советский ученый К. Ш. Зигангиров, а несколько позднее (1969 г.) аналогичное предложение сделал американский ученый Ф. Джелинек.

     Значительным  достижением в области теории кодирования явилась разработка в 1967 году одним из крупнейших американских ученых А. Витерби весьма эффективного с вычислительной точки зрения алгоритма декодирования сверточных кодов по максимуму правдоподобия. Этот алгоритм, в отличие от алгоритма последовательного декодирования, исследует все возможные пути по кодовой решетке на длине кодового ограничения k, поэтому он применим для декодирования сверточных кодов при сравнительно небольших значениях K = 1-10.

     Сверточные коды и алгоритмы Витерби и последовательного декодирования получили в настоящее время весьма широкое распространение в магистральных радиорелейных и спутниковых системах связи.

     Американский  ученый Д. Слепян, получивший значительные результаты в разных областях теории связи, был первым, кто в 1956 году заложил строгий фундамент теории линейных блочных кодов с проверкой на четность - математическую теорию групп.

     В 1957 году другой американец, Е. Прейндж, первый ввел понятие циклического кода и указал на его связь с идеалами алгебр. Циклические коды являются важным подклассом линейных кодов, которые имеют эффективные алгоритмы кодирования и декодирования, основанные на применении идей алгебраической теории полей Галуа. Значительный вклад в разработку теории этих кодов внесли американские ученые Пи-терсон, Берлекамп и Касами.