Файл: «Методы кодирования данных (Метод Шеннона-Фано).pdf

Введение

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

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

Основателем теории данных принято считать Клода Шеннона, который, начав с углубленного изучения математической статистики, предоставил инженерам полное определение ёмкости коммуникационного канала. Его теория не рассматривает содержание передаваемого сообщения и не обращает особого внимания на процессы передачи данных, но старается оптимизировать процессы сжатия сообщения с небольшими потерями, что требует применения критерия точности.

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

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

Поэтому изучение кодирования данных и методов кодирования данных является актуальным.

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

Предметом исследования являются программные приложения, показывающие основные принципы кодирования данных.

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

- раскрыть основные понятия кодирования данных;

- рассмотреть классификацию назначения и способы представления кодов;

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

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

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

Глава 1. Теоретические основы кодирования данных

1.1 Основные понятия кодирования данных

Кодирование данных - процесс преображения сигнала из вида, подходящего для конкретного применения данных, в форму, благоприятную для передачи, сохранения или автоматической обработки (цифровое кодирование, аналоговое кодирование, таблично-символьное кодирование, числовое кодирование). Процесс преобразования сообщения в комбинацию знаков в согласовании с кодом называется кодированием, процесс воссоздания сообщения из комбинации символов называется декодированием [10, c.17].

Данные следует отображать в каком-либо виде, т.е. кодировать.

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

Алфавит, с помощью которого представляются данные до преображения называется первичным; алфавит окончательного отображения – вторичным.

Код является правилом, описывающем соотношение знаков или их синтезирования одного алфавита знакам или их сочетаниям иного алфавита; или же знаки вторичного алфавита, применяемые для отображения знаков или их синтезов первичного алфавита.

Код – комплекс знаков (символов) и система поставленных правил, с использованием которых данные могут быть представлены (закодированы) в форме набора из таких символов для передачи, обрабатывания и сохранения. Окончательная последовательность кодовых знаков называется словом. Зачастую для кодирования данных применяют буквы, цифры, числа, знаки и их сочетания [10, c. 18].

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

Кодирование является операцией сравнения знаков или групп знаков одного кода с знаками или группами знаков иного кода.

Кодирование – перевод данных, отображенных в виде первичного алфавита, в последовательность кодов [16, c. 29].

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

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

Декодирование - действие, противоположное кодированию, т.е. восстановление данных из закодированной формы (возобновление в первичном алфавите по полученной очередности кодов) [16, c. 30].

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

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

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

Каждый код должен гарантировать единственное чтение сообщения (достоверность), так и, предпочтительно, быть экономным (применять в среднем минимальное число знаков на сообщение).

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

Компьютер может подвергать обработке только данные, представленные в числовой форме. Все другие данные для обработки на компьютере должны быть преобразованы в числовую форму. С использованием компьютерных программ можно трансформировать полученные данные, в том числе - текстовые. При введение в компьютер буква шифруется некоторым числом, а при отображении на внешние приборы (экран или печать) для восприятия людьми по данным числам отображаются изображения букв. Соотношение между набором букв и числами называется кодировкой символов. Обычно, все числа в компьютере отображаются с применением нулей и единиц, т.е. словами, компьютеры функционируют в двоичной системе счисления, потому что при этом приборы для их обработки выходят существенно более простыми [7, c. 61].

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

Кодирование данных делится на этапы:

1) Установление объёма данных, подлежащих кодированию.

2) Систематизация и группировка данных.

3) Подбор системы кодирования и построение кодовых обозначений.

4) Непосредственное кодирование [10, c. 20].

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

1.2 Классификация назначения и способы представления кодов

Коды классифицируют по разным признакам:

1. По основанию (числу знаков в алфавите): бинарные (двоичные m=2) и не бинарные (m № 2).

2. По длине кодовых комбинаций (слов): равные, когда все кодовые комбинации обладают равной длиной и неравные, когда протяженность кодовой комбинации не стабильна.

3. По способам передачи: поочередные и параллельные; блочные - данные сначала помещаются в буфер, а потом подаются в канал и бинарные непрерывные.

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

5. В связи с предназначением и применением [1, c. 36].

Условно выделяют следующие типы кодов:

1. Внутренние коды - коды, применяемые внутри устройств. К ним относятся машинные коды, а также коды, основывающиеся на применении позиционных систем счисления (двоичный, десятичный, двоично-десятичный, восьмеричный, шестнадцатеричный и др.). Известным кодом считается двоичный код, который дает возможность просто осуществить аппаратное устройство для хранения, обработки и передачи информации в двоичном коде. Он гарантирует большую надежность устройств и простоту исполнения операций над данными в двоичном коде. Двоичные данные, сведенные в группы по 4, формируют шестнадцатеричный код, который превосходно соответствует архитектуре ЭВМ, функционирующей с данными кратными байту (8 бит).

2. Коды для обмена данными и их передачи по каналам связи. Обширную популяризацию в ПК приобрел код ASCII (American Standard Code for Information Interchange). ASCII является 7-битным кодом буквенно-цифровых и иных символов. Так как ЭВМ функционируют с байтами, то 8-й разряд применяется для синхронизации или апробации на четность, или углубления кода. В ЭВМ фирмы IBM применяется раздвинутый двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code). В каналах связи часто применяется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модели (МТК и др.) [6, c. 49].

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

Коды для особых применений - это коды, определенные для решения особенных задач передачи и обрабатывания данных. Образцами подобных кодов считается циклический код Грея, часто применяемый в АЦП угловых и линейных перемещений. Коды Фибоначчи употребляются для возведения быстродействующих и помехоустойчивых АЦП.

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

Матричное отображение кодов. Применяется для отображения размеренных n - значных кодов. Для простого (полного и равномерного) кода матрица имеет n - столбцов и 2n - строк, т.е. код применяет все совокупности. Для помехоустойчивых (корректирующих, обнаруживающих и выправляющих ошибки) матрица охватывает n - столбцов (n = k+m, где k-число информативных, а m - число проверочных разрядов) и 2k - строк (где 2k - число разрешенных кодовых комбинаций). При крупных значениях n и k матрица станет чрезмерно массивной, при этом код вписывается в сокращенном виде. Матричное отображение кодов применяется, например, в линейных групповых кодах, кодах Хэмминга и т.д. [6, c. 51].

Отображение кодов в виде кодовых деревьев. Кодовое дерево - связной граф, не имеющий циклов. Связной граф - граф, в котором для любой пары вершин присутствует путь, объединяющий данные вершины. Граф складывается из узлов (вершин) и ребер (ветвей), объединяющих узлы, находящиеся на различных уровнях. Для возведения дерева размеренного двоичного кода находят вершину, именуемую корнем дерева (истоком) и из нее проводят ребра в следующие две вершины и т.д.