Файл: Методы кодирования данных (История кодирования и что это такое).pdf

Введение

Актуальность темы исследования обоснована тем, что кодирование используется абсолютно везде в нашей жизни и для этого применяются его разные методы. Мы постоянно занимаемся кодированием, например, человек мыслит весьма расплывчатыми понятиями, и, чтобы донести мысль до другого человека, мы применяем язык, как систему кодирования понятий. Также, чтобы записать слова языка, мы используем азбуку. Заниматься проблемой кодирования информации люди начали еще до изобретения электронных вычислительных машин. Надо понимать, что чертежи, ноты, математические выкладки являются тоже некоторым кодированием разных информационных объектов. Аналогично, универсальная система кодирования требуется для того, чтобы превратить одну информационную форму в другую или другими словами, преобразовать данные в вид, удобный для обработки, чтения и передачи. С созданием электронных вычислительных машин появилась потребность кодировать практически все типы информационных данных, с которыми связано всё мировое общество в целом. Для этого были придуманы разные методы кодирования данных, о которых и пойдет речь в данной курсовой.

В целом, методы кодирования данных довольно подробно исследованы в литературе, то есть исследуемая тема обладает высоким уровнем теоретической разработанности. Вопросам кодирования данных и его методам посвящен широкий ряд учебных пособий, научных статей, монографий и статей различных авторов. Абсолютно точно следует выделить труды следующих авторов: Р. Хэмминг, К. Шеннон, В.А. Котельников, Э. Борель, Э. Уиттекер, К. Огура.

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

Актуальность и степень разработанности проблемы обуславливают выбор объекта, предмета, целей и задач работы.

Объект исследования – кодирование данных.

Предмет исследования – методы кодирования данных.

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

В соответствии с этой целью в работе решаются следующие задачи:

- рассмотреть общие понятия кодирования

- изучить виды кодирования информации

- ознакомиться с историей кодирования данных

- разобрать и изучить методы кодирования данных

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

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

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

История кодирования и что это такое

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

Что такое кодирование и основные понятия

Итак, кодирование – это представление сигнала в определенной форме, удобной или пригодной для последующего использования сигнала. Говоря строже, это правило, описывающее отображение одного набора знаков в другой набор знаков. Тогда отображаемый набор знаков называется исходным алфавитом, а набор знаков, который используется для отображения, – кодовым алфавитом, или алфавитом для кодирования. При этом кодированию подлежат как отдельные символы исходного алфавита, так и их комбинации. Аналогично для построения кода используются как отдельные символы кодового алфавита, так и их комбинации. Совокупность символов кодового алфавита, применяемых для кодирования одного символа (или одной комбинации символов) исходного алфавита, называется кодовой комбинацией, или, короче, кодом символа. При этом кодовая комбинация может содержать один символ кодового алфавита. Процесс восстановления сообщения из комбинации символов называется декодированием.

Символ или комбинация символов исходного алфавита, которому соответствует кодовая комбинация, называется исходным символом.

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

Взаимосвязь символов (или комбинаций символов, если кодируются не отдельные символы исходного алфавита) исходного алфавита с их кодовыми комбинациями составляет таблицу соответствия (или таблицу кодов).

В качестве примера можно привести систему записи математических выражений, азбуку Морзе, морскую флажковую азбуку, систему Брайля для слепых и др. Азбука Морзе является общеизвестным кодом из символов телеграфного алфавита, в котором буквам русского языка соответствуют кодовые слова из «точек» и «тире».

Алфавит [alphabetos, от названий первых двух букв греческого А. - альфа и бета; аналогично: азбука — от аз и буки], совокупность графических знаков — букв (например, латинский, русский А.) или слоговых знаков (например, индийский А. деванагари), расположенных в традиционно установленном порядке.

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

Символы (в компьютере) - цифры, буквы, иероглифы и т.п.

Кодер - программист, специализирующийся на кодировании - написании исходного кода по заданным спецификациям.

Кодер - одна из двух компонент кодека (пары кодер – декодер).

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

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

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

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

С необходимостью кодирования данных впервые столкнулись более полутораста лет назад, вскоре после изобретения телеграфа. Каналы были дороги и ненадежны, что сделало актуальной задачу минимизации стоимости и повышения надёжности передачи телеграмм. Проблема ещё более обострилась в связи с прокладкой трансатлантических кабелей. С 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 американец Гарри Найквист уточнил принципы оцифровки и восстановления аналогового сигнала.