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

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

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

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

                                            выполнил:

                                            группа:  
 
 
 

Москва, 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 году другой американец, Е. Прейндж, первый ввел понятие циклического кода и указал на его связь с идеалами алгебр. Циклические коды являются важным подклассом линейных кодов, которые имеют эффективные алгоритмы кодирования и декодирования, основанные на применении идей алгебраической теории полей Галуа. Значительный вклад в разработку теории этих кодов внесли американские ученые Пи-терсон, Берлекамп и Касами.

     Весьма  важный и обширный класс линейных циклических кодов Боуза, Рой-Чоудхури (США, 1960 г.) и Хоквингема (Франция, 1959 г.), названный кодами БЧХ по первым буквам имени открывших их независимо ученых, позволял корректировать многократные ошибки в принятой кодовой комбинации. Эти коды имели следующие параметры: n = 2m - 1, k > 2m - 1 - mt, d > 2t + 1 (здесь n - длина кода, k - число информационных символов в кодовой комбинации, t - количество корректируемых ошибок, d - минимальное хэммингово расстояние между кодовыми комбинациями). Декодирование кодов БЧХ производят на основе решения определенных алгебраических уравнений.

     Были  построены специальные коды для  работы в каналах связи, в которых  возникают пакеты ошибок. Однако задача коррекции пакетов ошибок может  быть сведена к задаче коррекции  независимых ошибок путем применения метода перемежения символов, который  состоит в перестановке передаваемых символов таким образом, чтобы соседние символы передаваемой кодовой комбинации оказывались разнесенными в достаточной  степени во времени так, чтобы  их искажения в канале связи были независимыми. На приеме производится восстановление исходного порядка  символов. Эта простая идея, выдвинутая в 1960 году советскими учеными академиком А. А. Харкевичем и профессором Э. Л. Блохом и позднее (1970 г.) американским ученым Дж. Л. Рамсеем, сегодня применяется во многих системах радиорелейной и подвижной связи, в которых при приеме цифровых сигналов имеет место группирование ошибок.

     Сердцем любой цифровой системы связи  является аналоговый канал. Цифровая система  связи для такого канала включает модулятор/демодулятор (модем), преобразующий  аналоговый канал в дискретный так, чтобы можно было использовать кодер/декодер (кодек).

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

     Идеи  применения мягкого решения в  демодуляторе для декодирования  кодовых комбинаций зародились почти  с самого начала возникновения теории кодирования. Первой работой в этом направлении можно считать выполненное  в 1954 году американскими учеными  Сильверманом и Болсером исследование помехоустойчивости приема с мягким решением кода Вагнера, содержащего всего один избыточный двоичный символ для проверки информационных символов на четность. На приеме принимается жесткое решение о значениях всех принятых символов и, кроме того, дополнительно определяется наименее надежный из них. При декодировании этот символ изменяется на противоположный в том случае, если проверка принятой кодовой комбинации на четность не выполняется. При наличии всего одного проверочного символа в кодовой комбинации такой алгоритм декодирования позволял корректировать в ней одиночные ошибки. Эта идея была позже в обобщенном виде применена к декодированию кодов БЧХ в канале со стираниями ненадежно принятых символов.

     С конца 60-х - начала 70-х годов были выполнены многочисленные исследования, направленные на разработку методов  приема сигналов в целом. При этом в приемном устройстве решение о  приеме той или иной кодовой комбинации принимается по методу максимального  правдоподобия, то есть при декодировании  ищется такая кодовая комбинация, которая находится на наименьшем евклидовом расстоянии от принятого  сигнала. Учет структуры кода позволял существенно упростить вычисления этого расстояния.

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

     Для кодов с пороговым декодированием применение мягкого решения исследовалось  в США Дж. Л. Месси и несколько позже в СССР Л. М. Финком и Б. Д. Каганом.

     Для блочных кодов в начале 70-х  годов американскими учеными  Е. Велдоном и Д. Чейзом были предложены алгоритмы декодирования, использующие мягкое решение демодулятора и позволяющие приблизиться к решению по максимуму правдоподобия.

     С 80-х годов появилось новое научное  направление - разработка и анализ помехоустойчивости приема специально построенных сигналов, названных сигнально-кодовыми конструкциями. Это направление представляет собой  синтез методов модуляции, кодирования  и их оптимального приема и позволяет  создавать системы связи, в которых  по каналу связи, имеющему ограниченную полосу частот, возможно передавать информацию с качеством, приближающимся к потенциальному пределу, определяемому положениями теорий Котельникова и Шеннона.

     В 1982 году в результате теоретических  исследований американского ученого  Г. Унгербоека была создана решетчатая кодовая модуляция (РКМ). Этот вид модуляции основывается на сочетании многопозиционных сигналов и помехоустойчивых кодов. При этом ансамбль многопозиционных сигналов, содержащий М=2n сигналов, разбивается на K = 2k+1 вложенных подансамблей с монотонно возрастающими расстояниями. В качестве сигналов используются многопозиционная ФМ и КАМ. Информационная последовательность символов преобразуется в кодовую с помощью сверточного кода, который применяется к кодированию k из п информационных символов, причем сверточный код имеет скорость k/k+1 и вводит 1-битовую избыточность. Кодированные биты определяют выбор подансамбля, а некодированные - конкретную сигнальную точку в этом выбранном подансамбле. Для оптимального приема сигналов РКМ используется метод максимального правдоподобия, реализуемый в виде алгоритма Витерби. Применение РКМ позволяет (при заданных скорости передачи сигналов и вероятности ошибочного приема) уменьшить необходимые энергетику линии и полосу частот. Этот вид модуляции находит применение на магистральных высокоскоростных линиях радиорелейной и спутниковой связи.

     Весьма  обширные исследования помехоустойчивости различных методов приема сигнально-кодовых  конструкций в гауссовском канале связи были выполнены советскими учеными С. Л. Портным, В. В. Зябловым, В. В. Гинзбургом и В. Л. Банкетом.

     ЗАКЛЮЧЕНИЕ

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

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

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

     Рассмотренные выше этапы развития кодирования  как нельзя лучше показывают, что  с развитием кодирования произошло объединение интеллектуального и производственного потенциала разных стран для решения многих вопросов разработки перспективных технологий. Это объединение создало условия для взрывного развития и распространения на Земле средств связи.

     Список  литературы:

1. Быховский М.А. «Круги памяти. Очерки истории развития радиосвязи и вещания в XX столетии». Из серии «История электросвязи и радиотехники», выпуск 1. —М.: Мобильные коммуникации, 2001.
2. Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования. — Киев, Вища школа, 1986.
3.    Агеев В.М. Теория информации и кодирования: дискретизация и кодирование измерительной информации. — М.: МАИ, 1977.
4. Коган И.И. Прикладная теория информации. — М.: Радио и связь, 1981.