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

ВВЕДЕНИЕ

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

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

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

Объектом исследования в работе является область применения информационных технологий и средств вычислительной техники в обработке данных, обращающихся в современном информационном обществе.

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

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

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

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

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

Первым теоретическое решение проблемы передачи данных по зашумленным каналам связи предложил Клод Шеннон, основоположник статистической теории информации. Работая в Bell Labs в работе «Математическая теория передачи сообщений» (1948) Шеннон показал, что если пропускная способность канала связи выше энтропии источника сигнала, то сообщение можно закодировать таким способом, что оно будет передано без лишних задержек. Шеннон доказал, что при наличии канала с достаточной пропускной способностью сообщение может быть передано с некоторыми временными задержками. Кроме того, он показал возможность достоверной передачи при наличии шума в канале. Формула С = W log ((P+N)/N), высечена на скромном надгробии Шеннону, установленном в его родном городе в штате Мичиган.^[[3]]

Труды Шеннона легли в основу множества дальнейших исследований в области теории информации, но практического инженерного применение они не получили. Переход от теории к практике стал возможен благодаря усилиям Ричарда Хэмминга, коллеги Шеннона по 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, ЕСС). Современные модификации кодов Хемминга используются во всех системах хранения данных и для обмена между процессором и оперативной памятью. Один из их вариантов, коды Рида-Соломона применяются в компакт-дисках, позволяя воспроизводить записи без скрипов и шумов, вызванных царапинами и пылинками. Существует множество версий кодов, построенных на базе кодов Хэмминга, они различаются алгоритмами кодирования и количеством проверочных битов. Особое значение такие коды приобрели в связи с развитием дальней космической связи с межпланетными станциями.^[[4]]

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

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

2. Теория и практика кодирования данных

Одним из разделов теоретической информатики является Теория кодирования информации. К основным задачам, решаемым теорией кодирования информации, необходимо отнести следующие:

поиск наиболее экономичного метода кодирования информации;

согласование характеристик передаваемой информации с особенностями канала передачи информации;

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

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

2.1. Понятийный аппарат

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

Кодирование информации. Основные понятия.

Источник представляет сообщение в алфавите, который обозначается первичным, после чего это сообщение попадает в устройство, преобразующее и представляющее его во вторичном алфавите

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

• Кодирование перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.

• Декодирование - операция обратная кодированию.

• Кодер - устройство, обеспечивающее выполнение операции кодирования.

• Декодер устройство, производящее декодирование

Информацию необходимо представлять в какой-либо форме, т.е. кодировать.^[[7]]

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

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

Принципы оптимального кодирования.

Экономичность кода зависит от грамотной постановки последовательности вопросов.

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

1. Все сообщения упорядочиваются по убыванию их частот.
2. Совокупность сообщений последовательно делится на две равновероятные (в сумме) части, причем первой из них присваивается символ «0», а второй – «1». Если какая-либо часть содержит более одного сообщения, то она так же делится на части по тому же принципу. ^[[8]]

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

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

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

Кодирование - перевод информации, представленной посредством первичного алфавита, в последовательность кодов. ^[[9]]