Методы кодирования данных

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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]]

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

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

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

Шифрование - разновидность кодирования.

Шифр - код, значение и правила использования которого известно ограниченному кругу лиц.

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

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

Следовательно, кодирование предшествует передаче и хранению информации. При этом хранение связано с фиксацией некоторого состояния носителя информации, а передача — с изменением состояния во времени (т.е. процессом). Эти состояния или сигналы будем называть элементарными сигналами - именно их совокупность и составляет вторичный алфавит. ^[[10]]

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

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

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

Математическая постановка задачи кодирования.

• А - первичный алфавит. Состоит из N знаков со средней информацией на знак I^A.

• В- вторичный из М знаков со средней информацией на знак I^B.

• Сообщение в первичном алфавите содержит m знаков, а закодированное - m знаков.

• I_s(A) - информация в исходном сообщении. I_f(B) - информация в закодированном сообщении.

• I_s(A) ≤ I_f(B) – условие обратимости кодирования, т.е. не исчезновения информации.

• n * I(A) ≤ m * I(B) (заменили произведением числа знаков на среднее информационное содержание знака).

• m/n – характеризует среднее число знаков вторичного алфавита, который используется для кодирования одного знака первичного. Обозначим его K (A, B)

• K (A, B) ≥ I(A) / I(B) Обычно K (A, B) > 1.

• K^min (A, B) = I^(A) / I^(B) – минимальная длина кода.

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

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

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

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

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

1. Определение объёма информации, подлежащей кодированию.
2. Классификация и систематизация информации.
3. Выбор системы кодирования и разработка кодовых обозначений.
4. Непосредственное кодирование.

2.2. Алфавит в теории информации

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

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

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

Тогда:

К^min (А, В)= I ^(А) / log₂ М= I ^(А), здесь I – средняя

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

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

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

Начнём с самого грубого приближения (будем называть его нулевым) предположим, что появление всех знаков (букв) алфавита в сообщении равновероятно. Тогда для английского алфавита n_e=27 (с учетом наличия пробела как самостоятельного знака); для русского алфавита n_r=34. Из формулы Хартли

I = log₂ n (2.1)

находим:

I₀^(e)= log₂27 = 4,755 бит.

I₀^(r)= log₂34 = 5,087 Сит.

В результате получаем, что в нулевом приближении со знаком русского алфавита в среднем связано больше количество информации, чем со знаком английского языка. Например, в русской букве «а» информации больше, чем в «а» английской! Это, безусловно, не означает, что английский язык - язык Шекспира и Диккенса — беднее, чем язык Пушкина и Достоевcкого. Лингвистическое богатство языка определяется количеством слов и их сочетаний, а это никак не связано с числом букв в алфавите. С точки зрения техники это означает, что сообщения из равного количества символов будет иметь разную длину (и соответственно, время передачи) и большими они окажутся у сообщений на русском языке.

В качестве следующего (первого) приближения, уточняющего «нулевое», попробуем учесть то обстоятельство, что относительная частота или вероятность появления различных букв в тексте (или сообщении) неодинакова. Рассмотрим таблицу средних частот (вероятностей) появления букв для русского алфавита, в который включен также знак «пробел» для разделения слов; с учетом неразличимости букв «е» и «ё», а также «ь» и «ъ» (так принято в телеграфном кодировании), получим алфавит из 32 знаков со следующими вероятностями их появления в русских текстах:

Табл. 2.1 Частота появления букв

Буква	Частота	Буква	Частота	Буква	Частота	Буква	Частота
пробел	0,175	о	0,090	е, ё	0,072	а	0,062
и	0,062	т	0,053	н	0,053	с	0,045
р	0,040	в	0,038	л	0,035	к	0,028
м	0,026	д	0,025	п	0,023	у	0,021
я	0,018	ы	0.016	з	0,016	ъ, ь	0,014
б	0,014	г	0,013	ч	0,012	й	0,010
x	0,009	ж	0,007	ю	0,006	ш	0,006
ц	0,004	щ	0,003	э	0,003	ф	0,002

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

I = (2.2)

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

Из неё, к примеру, следует, что если р, — вероятность (относительная частота появления) знака номер i данного алфавита из N знаков, то среднее количество информации, приходящейся на один знак, равно:

(2.3)

- формула К. Шеннона.

Теорема Шеннона (переформулировка).

При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.^[[14]]

Применение формулы (2.3) к алфавиту русского языка дает значение средней информации на знак I_i^(r) = 4,36 бит, а для английского языка I_i^(e) = 4,04 бит, для французского I_i^(f) = 3,96 бит, для немецкого I_i^(d) = 4,10 бит, для испанского I_i^(s) = 3,98 бит. Как мы видим, и для русского, и для английского языков учёт вероятностей появления букв в сообщениях приводит к уменьшению среднего информационного содержания буквы, что, кстати, подтверждает справедливость формулы (2.3). Несовпадение значений средней информации для английского, французского и немецкого языков, основанных на одном алфавите, связано с тем, что частоты появления одинаковых букв в них различаются.

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

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

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

Особенности вторичного алфавита при кодировании.

1. Элементарные коды 0 и 1 могут иметь одинаковые длительности

(t0 = t1) или разные (≠);

2. Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код);

3. Коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование).

Последующие (второе и далее) приближения при оценке значения информации, приходящейся на знак алфавита, строятся путем учета корреляций, т.е. связей между буквами в словах. Дело в том, что в словах буквы появляются не в любых сочетаниях; это снижает неопределенность определения следующей буквы после нескольких других, например, в русском языке нет слов, в которых встречается сочетание «щц» или «фъ». И напротив, после некоторых сочетаний можно с большей вероятностью предположить возможность появления следующей буквы, например, после распространенного сочетания «пр» непременно следует гласная буква, а их в русском языке всего 10 и, следовательно, вероятность определения следующей буквы 1/10, а не 1/33. В следствие этого примем следующее определение:

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

Учёт в английских словах двухбуквенных сочетаний понижает среднюю информацию на знак до значения I₂^(e) = 3,32 бит, учёт трехбуквенных до I₂^(e)=3,10 бит. Шеннон сумел приблизительно оценить пятибуквенные сообщения I₅^(e) ≈ 2,1 бит и восьмибуквенные I₈^(e) ≈ 1,9 бит. Аналогичные исследования для русского языка дают: I₂^(r) = 3,52 бит; I₃^(r) = 3,01 бит.

Последовательность I₀, I₁, I₂,... является убывающей в любом языке. Перекладывая её на учёт бесконечного числа корреляций, можно оценить предельную информацию на знак в данном языке I_∞, которая будет отражать минимальную неопределенность, связанную с выбором знака алфавита без учета семантических особенностей языка, в то время как I₀ является другим предельным случаем, поскольку характеризует наибольшую информацию, которая может содержаться в знаке данного алфавита. Шеннон ввел величину, которую обозначил относительной избыточностью языка:

(2.4)

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

Рассмотри проблему непосредственно передачи информации.

Для рассмотрения вопросов передачи информации удобно ппредположить, что получатель задает отправителю вопросы, допускающие только ответы «да» или «нет», так что отправителю остается только выбирать ответы в соответствии со смыслом передаваемого сообщения. ^[[15]]

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

Например, чтобы угадать задуманное число от 1 до 100 неразумно спрашивать про все числа по очереди: “Это не «0»?”. ‘А может «1»?". Гораздо разумнее разбить числа на группы и последовательно сужать поиск например - "Это число больше 50?” — “Нет”, “Оно больше 25?” и т.д. Важно, что последовательность вопросов (код) заготовлена и согласована с получателем.

Исследования Шеннона для английского языка дали значение I_∞ ≈ 1,4 ÷ 1,5 бит, что по отношению I₀ = 4,755 бит создает избыточность 0,68. Подобные оценки указывают, что и для других европейских языков, в том числе русского, избыточность составляет 60 — 70%. Это означает, что возможно почти трехкратное сокращение текстов при кодировании без значительного ущерба для их содержательной части и выразительности. Например, телеграфные тексты делаются меньше за счёт неиспользования союзов и предлогов без ущерба для смысла; в них же используются однозначно расшифровываемые сокращения «ЗПТ» и «ТЧК» вместо полных слов (эти сокращения приходится использовать, поскольку знаки «.» и «,» не входят в телеграфный алфавит). Однако такое «экономичное» представление слов понижает разборчивость языка, уменьшает возможность распознавания речи при наличии шума (а это одна из проблем передачи информации по реальным линиям связи), а также исключает возможность локализации и исправления ошибки (написания или передачи) при её возникновении. Именно избыточность языка позволяет легко восстановить текст, даже если он содержит большое число ошибок или неполон. В этом смысле избыточность есть определенная страховка и гарантия разборчивости.

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

2.3. Двоичная система счисления

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

Не станем рассматривать все существующие системы счисления, а сразу перейдём к двоичной системе, по причине того, что именно она широко применяется в практике кодирования сигналов.

Двоичная система счисления - это позиционная система счисления с основанием 2.

Позиционная система счисления — система счисления, в которой один и тот же числовой знак или цифра в записи числа имеет различные значения в зависимости от того разряда, где он расположен.

В такой системе счисления натуральные числа записываются с помощью двух символов (в роли которых обычно выступают цифры «0» и «1»).

Двоичная система применяется в цифровых устройствах, так как является наиболее простой и соответствует требованиям следующим требованиям: 1) Чем меньше значений существует в системе, тем проще изготовить отдельные элементы, оперирующие этими значениями. Например, две цифры двоичной системы счисления могут быть легко представлены многими физическими явлениями: есть ток — нет тока, индукция магнитного поля больше пороговой величины или нет и т. д. 2) Чем меньше количество состояний у элемента, тем выше помехоустойчивость и тем быстрее быстродействие. Например, чтобы закодировать три состояния через величину индукции магнитного поля, потребуется ввести два пороговых значения, что не будет способствовать помехоустойчивости и надёжности хранения информации. 3) Двоичная арифметика является довольно простой. Простыми являются таблицы сложения и умножения - основных действий над числами. 4) Возможно использование аппарата алгебры логики для вычисления побитовых операций над числами.^[[16]]

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

1 + 0 = 0

1 + 1 = 10

10 + 10 = 100

Таблица умножения двоичных чисел .

0 * 0 = 0

0 * 1 = 0

1 * 0 = 0

1 * 1 = 1

К примеру, при использовании двоичной системы при измерении дюймами при указании линейных размеров в дюймах по традиции используют двоичные дроби, а не десятичные, например: 5¾̋ , 7 ̋ , 3 ̋ и т.д.

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

2.2. Таблица степеней основания «2»

512

256

128

64

32

16

8

4

2

1

Начиная с цифры 1 все цифры умножаются на два. Точка, которая стоит после «1» называется двоичной точкой.

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

Допустим, нам дано двоичное число 110001. Для перевода его в десятичное число просто запишите его справа налево как сумму по разрядам следующим образом:

1 * 2⁰ + 0 * 2¹ + 0 * 2² + 0 * 2³ + 1 * 2⁴ + 1 * 2⁵ = 1 + 0 + 0 + 0 + 16 + 32 = 49.

Можно записать это в виде таблицы следующим образом:

512	256	128	64	32	16	8	4	2	1
				1	1	0	0	0	1
				+32	+16				+1

Точно так же, начиная с двоичной точки, двигайтесь справа налево. Под каждой двоичной единицей напишите её эквивалент в строчке ниже. Сложите получившиеся десятичные числа. Таким образом, двоичное число 110001 равнозначно десятичному 49.

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

Например, двоичное число 1011011 переводится в десятичную систему так:

0*2+1=1>>1*2+0=2>>2*2+1=5>>5*2+1=11>>1l*2+0=22»22*2+l=45>> 45*2+1=91. В десятичной системе это число будет записано как 91. Или число 101111 переводится в десятичную систему так: 0*2+1=1>>1*2+0=2>>2*2+1 =5>>5*2+1=11>>11*2+1=23>>23*2+1=47 То есть в десятичной системе это число будет записано как 47. ^[17]

Предположим, нужно перевести число 19 в двоичное. Следует воспользоваться следующей процедурой:

19/2 = 9 с остатком 1

9 /2 = 4 с остатком: 1

4 /2-2 с остатком 0

2/2-1 с остатком 0

1 /2 - 0 с остатком: 1

Таким образом, мы делим каждое частное на 2 и записываем в остаток 1 или 0. Продолжать деление надо пока в делимом не будет 1. Ставим числа из остатка друг за другом, начиная с конца. В результате получаем число 19 в двоичной записи (начиная с конца): 10011.

2.4. Кодирование сигнала

Кодирование сигнала — есть его представление в некоторой форме, удобной для дальнейшего использования сигнала, т.е. это правило, описывающее представления одного набора знаков в другой набор знаков. Таким образом отображаемый набор знаков называется исходным алфавитом, а набор знаков используемый для отображения, - кодовым алфавитом, или алфавитом для кодирования. При этом кодированию подлежат как отдельные символы исходного алфавита, так и их различные комбинации. Соответственно для построения кода используются как отдельные символы кодового алфавита, так и их комбинации. К примеру, существует таблица соответствия между натуральными числами трёх систем счисления. Эту таблицу возможно рассматривать как определенное правило, описывающее отображение набора знаков десятичной системы счисления в двоичную и шестнадцатеричную. Тогда исходный алфавит - десятичные цифры от 0 до 9, а кодовые алфавиты - это 0 и 1 для двоичной системы; цифры от 0 до 9 и символы {А, В, С, D, Е, F} - для шестнадцатеричной. ^[[18]]

Кодовой комбинацией (кодом) называется совокупность символов кодового алфавита, используемы для кодирования одного символа (или одной комбинации символов) исходного алфавита. Вместе с этим кодовая комбинация может содержать один символ кодового алфавита. Исходным символом называется символ (или комбинация символов) исходного алфавита, которому соответствует кодовая комбинация. Например, поскольку 8 — 10002 и 8 является исходным символом, 10008 - это кодовая комбинация, или код, для числа 8. В это же время 8 - это исходный символ. Совокупность кодовых комбинаций называется кодом. Взаимосвязь символов (или комбинаций символов, если кодируются не отдельные символы) исходного алфавита с их кодовыми комбинациями составляет таблицу соответствия (таблицу кодов). Обратная процедура получения исходных знаков но кодам символов называется декодированием. Как видно, для выполнения правильного декодирования код должен быть однозначным, т.е. единственному исходному символу должен соответствовать единственный код и наоборот.

В зависимости от целей кодирования, различают следующие его виды:

- кодирование по образцу - используется всякий раз при вводе информации в компьютер для её внутреннего представления;

- криптофафическое кодирование, или шифрование, — используется, когда нужно защитить информацию от несанкционированного доступа;

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

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

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

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

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

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

Данная теорема дает принципиальную возможность оптимального кодирования. Но она не дает представление, как такое кодирование осуществить на практике — для решения этой задачи необходимо применение иных соображений.^[[19]]

Далее в работе ограничимся ситуацией, когда М - 2, т.е. для представления кодов в линии связи используется лишь два типа сигналов - с практической точки зрения это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть это импульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать «О» и «1», но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log₂M=l); тогда из теоремы Шеннона:

I_i^(A) ≤ K ⁽²⁾

и первая теорема Шеннона получает следующую интерпретацию:

При отсутствии помех передачи средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.^[20]

В двоичной системе кодирования:

Установление объема переданной информации при двоичном кодировании сводится к обычному подсчету числа импульсов (единиц) и пауз (нулей). В этом случае возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) отдельных кодов. Приемное устройство фиксирует интенсивность и длительность сигналов. Элементарные сигналы (0 и 1) могут иметь одинаковые или разные длительности. Их количество в коде (длина кодовой цепочки), который ставится в соответствие знаку первичного алфавита, также может быть тождественным (в этом случае код называется равномерным) или разным (неравномерный код). Наконец, коды могут строиться для каждого знака исходного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов). В результате при кодировании (алфавитном и словесном) возможны следующие варианты сочетаний:

Табл. 2.3 Варианты сочетаний

Длительности элементарных сигналов	Кодировка первичных символов (слов)	Ситуация
одинаковые	равномерная	(1)
одинаковые	неравномерная	(2)
разные	равномерная	(3)
разные	неравномерная	(4)

В случае применения неравномерного кодирования или сигналов разной длительности (ситуации (2), (3) и (4)) для отделения кода одного знака от другого между ними необходимо передавать специальный сигнал - временной разделитель (признак конца знака) или применять такие коды, которые оказываются уникальными, т.е. несовпадающими с частями других кодов. При равномерном кодировании одинаковыми по длительности сигналами (ситуация (1)) передачи специального разделителя не требуется, поскольку отделение одного кода от другого производится по общей длительности, которая для всех кодов оказывается одинаковой (или одинаковому числу бит при хранении).

Длительность двоичного элементарного импульса (τ) показывает, сколько времени требуется для передачи 1 бит информации. Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время К^(r)τ, Таким образом, можно построить такую систему кодирования, чтобы суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей.

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

3. Методы кодирования информации

Ранее средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения, но с появлением компьютеров ситуация радикально изменилась. К примеру десятичная позиционная система счисления — это универсальный способ кодирования чисел, в том числе натуральных. Римские цифры — другой способ кодирования небольших натуральных чисел, причём гораздо более наглядный и естественный: палец — I, пятерня — V, две пятерни — X. Однако при этом способе кодирования трудно выполнять арифметические операции над большими числами, поэтому он был вытеснен позиционной десятичной системой.^[[21]]

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

представление данных произвольной природы (например чисел, текста, графики) в памяти компьютера;

защита информации от несанкционированного доступа;

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

сжатие информации в базах данных.

Не ограничивая общности, задачу кодирования можно сформулировать следующим образом:

Пусть заданы алфавиты А = {a₁,... ,a_n}, В = {b₁,..., b_m} и функция F: А* → В*, причём Dom f = S, где S — некоторое множество слов в алфавите A, S А*. Тогда функция F называется кодированием, элементы множества S — сообщениями, а элементы = F(), S, В* — кодами (соответствующих сообщений). Обратная функция F^-1 (если она существует!) называется декодированием. Если |В| — m, то F называется m-ичным кодированием. Наиболее распространенный случай В = {0,1} — двоичное кодирование. Именно этот случай рассматривается в последующих разделах; слово «двоичное» опускается. Типичная задача теории кодирования формулируется следующим образом: при заданных алфавитах А, В и множестве сообщений S найти такое кодирование F, которое обладает определёнными свойствами (то есть удовлетворяет заданным ограничениям) и оптимально в некотором смысле. Критерий оптимальности, как правило, связан с минимизацией длин кодов. Свойства, которые требуются от кодирования, бывают самой разнообразной природы:

Существование декодирования, или однозначность кодирования: функция кодирования F обладает тем свойством, что ₁ ≠ ₂ => F(₁) ≠ (₂). Это очень естественное свойство, несмотря на это даже оно требуется не всегда. К примеру, трансляция программы на языке высокого уровня в машинные команды — это кодирование, для которого не требуется однозначного декодирования.

Помехоустойчивость, или исправление ошибок: продолжение функции декодирования F^-l обладает таким свойством, что F^-1() = F^-1( '), где ImF, В* \ Im F, если ' в определённом смысле близко к .

Заданная сложность (или простота) кодирования и декодирования. К примеру, в криптографии изучаются такие способы кодирования, при которых функция F вычисляется просто, но определение значения функции F^-1 требует многим более сложных вычислений.

Большое значение для задач кодирования имеет природа множества сообщений S. При одних и тех же алфавитах А, В и требуемых свойствах кодирования F оптимальные решения для разных S могут разительно отличаться. Для описания множества S (как правило, очень большого или бесконечного) применяются различные методы:

теоретико-множественное описание, например S={ | А* & | | = n };

вероятностное описание, например S = А*, и заданы вероятности p_i появления букв a_i в сообщении,

логико-комбинаторное описание, например S задано порождающей формальной грамматикой.^[22]

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

3.1. Алфавитное кодирование

Кодирование F может сопоставлять код всему сообщению из множества S как единому целому или же строить код сообщения из кодов его частей. Элементарной частью сообщения является одна буква алфавита А. Этот простейший случай будет рассматриваться в работе неоднократно.

Таблица кодов.

Алфавитное (или побуквенное) кодирование задается схемой (или таблицей кодов) :

( _{1 1},..., _{n n}), _i A, _i В*.

Множество кодов букв V {_i } называется множеством элементарных кодов (множеством кодовых слов). Алфавитное кодирование пригодно для любого множества сообщений S:

F: А* В*, _i1 .. ._1k = A*, F() _i1, ... _ik.

Рассмотрим алфавиты А: ={0,1,2,3,4,5, б, 7,8,9}, В: ={0,1} и схему

₁: = 0,1 1,2 10,3 11,4 100,5 101,6 110,7 111,8 1000,9> .

Эта схема однозначна, но кодирование не является взаимно-однозначным:

F₁ (333) = 111111 = F₁ (77),

а значит, декодирование невозможно. С другой стороны, схема

₂: = 0000,1 0001,2 0010,3 0011,4 0100,5 0101,6 0110,7 0111,8 1000,9> .

известная под названием «двоично-десятичное кодирование», допускает однозначное декодирование.

Разделимые схемы.^[[23]]

Рассмотрим схему алфавитного кодирования и различные слова, составленные из элементарных кодов. Схема называется разделимой, если

… = … => k = l & t 1…k (i₁…i_t),

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

Префиксные схемы.

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

Пример. Разделимая, но не префиксная схема:

A = {а,b}, В = {0,1}, = .

Неравенство Макмиллана.

Чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли определённому соотношению, известному как неравенство Макмиллана.

Азбука Морзе.^[[24]]

В качестве примера использования кодирования с неравной длительностью элементарных сигналов рассмотрим телеграфный код Морзе («азбука Морзе»), в этом методе каждой букве или цифре сопоставляется некоторая последовательность кратковременных импульсов — точек и тире, разделяемых паузами. Длительности импульсов и пауз различны: если продолжительность импульса, соответствующего точке, обозначить то длительность импульса тире составляет З, длительность паузы между точкой и тире , пауза между буквами слова З, пауза между словами (пробел) - 6. Таким образом, под знаками кода Морзе следует понимать: «.» - «короткий импульс + короткая пауза», «-» - «длинный импульс + короткая пауза», «0» - «длинная пауза», т.е. код оказывается троичным.

Этот код Морзе изобрел в 1838 г., т.е. задолго до исследований относительной частоты появления различных букв в текстах. Однако им был правильно выбран принцип кодирования — буквы с наибольшей частотой появления должны иметь более короткие коды, чтобы сократить совокупное время передачи. Относительные частоты букв английского алфавита он оценил простым подсчетом символов в ячейках типографской наборной машины. Поэтому самая распространенная английская буква «Е» получила код «точка». При составлении кодов Морзе для букв русского алфавита учёт относительной частоты появления букв не производился, что, конечно, повысило его избыточность. На подобии рассмотренных ранее вариантах кодирования, осуществим оценку избыточности. По-прежнему для удобства сопоставления данные представим в приведенном ниже формате. Признак конца буквы («0») в их кодах не отображается, но учтён в величине k_i, - длине кода буквы i.

Среднее значение длины кода k³ = 3,361. Предполагая возникновение знаков вторичного алфавита равновероятным, получаем среднюю информацию на знак равной I⁽²⁾ = log₂3 = 1,585 бит. Так как для русского алфавита I_l⁽¹⁾ — 4,356 бит, то:

Q^(r)= 1 -4,356/(3,361 - 1,585) 0,182

т.е. избыточность составляет около 18% (для английского языка *15%). Тем не менее, код Морзе имел в недавнем прошлом очень широкое распространение в ситуациях, когда источником и приемником сигналов являлся человек (не техническое устройство) и на первый план выдвигалась не экономичность кода, а удобство его восприятия человеком.

Табл. 3.1 Азбука Морзе

Буква	Код	pi*103	ki	Буква	Код	pi*103	ki
пробел	00	174	2	я	. - . -	16	5
о	---	90	4	ы	- . - -	16	5
е	.	72	2	з	- - .	16	4
а	.-	62	3	ь,ъ	- . . -	14	5
и	. .	62	3	б	- . . .	14	5
т	-	53	2	г	- - .	13	4
н	- .	53	3	ч	- - - .	12	5
с	. . .	45	4	й	. - - -	10	5
р	. - .	40	4	х	. . . .	9	5
в	. - -	38	4	ж	. . . -	7	5
л	. - . .	35	5	ю	. . - -	6	5
к	- . -	28	4	ш	- - - -	6	5
м	- -	26	2	ц	- . - .	4	5
д	- . .	25	4	щ	- - . -	3	5
п	. - -	23	4	э	. . - . .	3	6
у	. . -	21	4	ф	. . - .	2	5

3.2. Помехоустойчивое кодирование

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

Кодирование с исправлением ошибок.

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

K K′, K, K′ B*,

где К —множество переданных, а К' — соответствующее множество принятых по каналу сообщений, подразумевая, что разные вызовы «функции» С с одним и тем же аргументом могут возвращать различные результаты. Кодирование F (вместе с декодированием F^-1), обладающее тем свойством, что

S K K′ S, s A* (F^-1 C(F(s))) = s),

называется помехоустойчивым, или самокорректирующимся, или кодированием с исправлением ошибок. Без ограничения общности можно считать, что А = В = {0,1}. Кроме того, естественно предположить, что содержательное кодирование (вычисление F и F^-l) выполняется на устройстве, свободном от помех, то есть F и F^-l являются функциями в обычном смысле. Функция F^-1 является декодированием для кодирования F, но она не является обратной функцией для функции F.^[25]

Если про источник помех С ничего не известно, то функции F и F^-1 не могут быть определены, за исключением тривиальных случаев, когда S = или |S| = 1. Таким образом, для решения поставленной задачи необходимо иметь описание возможных ошибок (проявлений помех).

Ошибки в канале могут быть следующих типов:

0 → 1, 1 → 0 — ошибка типа замещения разряда;

0 → , 1 → — ошибка типа выпадения разряда;

→ 0, → 1 — ошибка типа вставки разряда.

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

Допустим, что имеется канал с характеристикой = (1,0,0), то есть в канале возможно не более одной ошибки типа замещения разряда при передаче сообщения длины n. Пусть требуется передавать через этот канал поток сообщений, каждое длины n. Рассмотрим следующее кодирование: F(): = ааа (то есть каждый разряд в сообщении утраивается) и декодирование

F^-1(abc): = : = a + b + с > 1 (то есть разряд восстанавливается методом «голосования»). Это кодирование кажется помехоустойчивым для данного канала, однако на самом деле это не так. Дело в том, что хотя можно предполагать, что при передаче сообщения длины 3n возможно не более 3 ошибок типа замещения разряда, но места этих ошибок совершенно необязательно распределены равномерно по всему сообщению. Ошибки замещения могут произойти в соседних разрядах, и метод голосования восстановит разряд неверно. Чтобы метод голосования сработал, вместо одного сообщения длины Зn придётся передать 3 сообщения длины n, то есть уменьшить втрое скорость передачи потока сообщений через канал.

Возможность исправления всех ошибок.

Пусть — множество слов, которые могут быть получены из слова s в результате всех возможных комбинаций допустимых в канале ошибок типа , то есть s S A*, В*. Если s' , то кратчайшую последовательность ошибок, которая позволяет получить из слова s слово s', будем обозначать . Заметим, что таких последовательностей может быть несколько. Другими словами,

=

Количество ошибок в кратчайшей последовательности обозначим ||. Если характеристика канала подразумевается, то индекс не указывается.

Пример. Пусть 5 — (2,1,1) для слов длины 2. Тогда |F5(01,10)| = 2, причём существует несколько различных кратчайших последовательностей ошибок, в частности: 01 —> 11 —> 10; 01 —у 1 —у 10; 01 —у 010 —у 10.

Пример. Рассмотрим канал, для которого в любом передаваемом разряде происходит ошибка типа замещения с вероятностью р, причём замещения различных разрядов статистически независимы. Данный канал называется двоичным симметричным. В этом случае любое слово s может быть преобразовано в любое другое слово s' ; замещениями разрядов. Таким образом, s (E_s = ), исправить все ошибки в двоичном симметричном канале не представляется возможным даже при сколь угодно малом р > 0.

Положим, что F является кодированием с исправлением р ошибок типа , если существует декодирование F^-1 такое, что

s S ( s′ (| | ≤ p => F^-1(s′) = s))^[26]

3.3. Сжатие данных

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

Сжатие текстов.^[[27]]

Предположим, что существует некоторое сообщение, закодированное каким-то общепринятым способом (для текстов это, например, код ASCII) и хранящееся в энергонезависимой памяти компьютера. Отметим, что равномерное кодирование (в частности, ASCII) не является оптимальным для текстов. Очевидно, в текстах обычно используется существенно меньше, чем 256 символов (в зависимости от языка — примерно 60-80 с учётом знаков препинания, цифр, строчных и прописных букв). Кроме того, частота появления букв различны, и для каждого естественного языка определены (с некоторой точностью) частоты появления букв в тексте. Таким образом, можно задаться некоторым набором букв и частотами их возникновения в тексте и с помощью алгоритма Хаффмена представить оптимальное алфавитное кодирование текстов (для заданного алфавита и языка). Нетрудные расчёты показывают, что такой метод кодирования для распространенных естественных языков будет иметь цену кодирования несколько меньше 6, то есть даст выигрыш по сравнению с кодом ASCII на 25% или несколько больше.

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

Известно, что практические программы сжатия (rar, zip и др.) имеют намного более лучшие показатели, чем код Хаффмена: при сжатии текстов коэффициент сжатия достигает более 70%. Это означает, что в таких программах используется не алфавитное кодирование.

Предварительное построение словаря

Рассмотрим следующий способ кодирования:

1. Исходное сообщение по некоторому алгоритму разбивается на последовательности букв, называемые словами (слово может иметь одно или несколько вхождений в исходный текст сообщения).

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

3. Далее код сообщения строится как пара — код словаря и последовательность кодов слов из данного словаря.

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

Допустим, что требуется кодировать тексты на русском языке. В качестве алгоритма деления на слова примем естественные правила языка: слова отделяются друг от друга пробелами или знаками препинания. Можно принять допущение, что в каждом конкретном тексте имеется не более 216 различных слов (обычно гораздо меньше). Таким образом, каждому слову можно сопоставить номер — целое число из двух байтов (равномерное кодирование). Поскольку в среднем слова русского языка состоят более чем из двух букв, такое кодирование даёт существенное сжатие текста (около 75% для обычных текстов на русском языке). Если текст достаточно велик (сотни тысяч или миллионы букв, то есть сотни и тысячи страниц), то дополнительные затраты на хранение словаря оказываются сравнительно небольшими.

Данный метод попутно позволяет решить задачу полнотекстового поиска, то есть определить, содержится ли заданное слово (или слова) в данном тексте, причём для этого не нужно просматривать весь текст (достаточно просмотреть только словарь).^[[28]]

Указанный метод можно усовершенствовать следующим образом. На шаге 2 следует применить алгоритм Хаффмена для построения оптимального кода, а на шаге 1 — решить экстремальную задачу разбиения текста на слова таким образом, чтобы среди всех возможных разбиений выбрать то, которое даёт наименьшую цену кодирования на шаге 2. Такое кодирование будет «абсолютно» оптимальным. К сожалению, указанная экстремальная задача очень трудоёмка, поэтому на практике не используется — время на предварительную обработку большого текста оказывается чрезмерно велико даже при использовании современных быстродействующих компьютеров

3.4. Шифрование

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

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

Поставить между злоумышленником и данными в компьютере «логический» барьер, то есть проверять наличие прав на доступ к данным и блокировать доступ при отсутствии таких прав. Для этого применяются различные системы паролей, регистрация и идентификация пользователей, разграничение прав доступа и т. п. Практика показывает, что борьба между «хакерами» и разработчиками модулей защиты операционных систем идёт с переменным успехом.^[29]

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

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

Криптография.^[30]

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

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

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

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

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

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

Шифрование с помощью случайных чисел.

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

T_i+1: =(а * Т_i+ b ) mod с,

где T_i — предыдущее псевдослучайное число, T_i+1 — следующее псевдослучайное число, а коэффициенты а, b, c - постоянны и хорошо известны. Обычно с = 2ⁿ, где n — разрядность процессора, a mod 4 = 1, а b — нечётное. В этом случае последовательность псевдослучайных чисел имеет период с.

Процесс шифрования определяется следующим образом. Шифруемое сообщение представляется в виде последовательности слов S₀,S₁,..., каждое длины n, которые поразрядно складываются по модулю 2 со словами последовательности T₀,T₁,..., то есть

C_i: = S_{i +2} T_i.

Последовательность Т₀, Т₁,... называется гаммой шифра.

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

S_i: = C_{i +2} T_i.

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

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

Если период последовательности псевдослучайных чисел достаточно велик, чтобы гамма шифра была длиннее сообщения, то дешифровать сообщение можно только подбором ключа. При увеличении п экспоненциально увеличивается криптостойкость шифра.^[31]

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

Криптостойкость.

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

Т_i: = С_{i +2} S_i,

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

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

Для повышения криптостойкости симметричных шифров применяют различные приёмы:

1. Вычисление гаммы шифра по ключу более сложным (или секретным) способом.

2. Применение вместо +2 более сложной (но обратимой) операции для вычисления шифровки.

3. Предварительное перемешивание битов исходного сообщения по фиксированному алгоритму.

Наиболее надёжным симметричным шифром считается DES (Data Encryption Standard), в котором используется сразу несколько методов повышения криптостойкости.

Модулярная арифметика.^[32]

Для объяснения метода шифрования с открытым ключом нужны некоторые факты из теории чисел, изложенные здесь без доказательств.

В этом подразделе рассматриваются только целые числа. Говорят, что число а сравнимо по модулю n с числом b (обозначение а = b mod n), если а и b при делении на n дают один и тот же остаток:

а = b mod n = a mod n = b mod n

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

Отношение сравнимости рефлексивно, симметрично и транзитивно и является отношением эквивалентности. Классы эквивалентности по отношению сравнимости (по модулю n) называются вычетами (по модулю n). Множество вычетов по модулю n обозначается Z_n. Обычно из каждого вычета выбирают одного представителя — неотрицательное число, которое при делении на n дает частное 0. Это позволяет считать, что Z_n = {0,1,2,... ,n — 1}, и упростить обозначения. Над вычетами (по модулю n) определены операции сложения и умножения по модулю n, обозначаемые, соответственно, +n и -n и определяемые следующим образом:

a _+n b (а + b) mod n, a_*nb f (а * b) mod n.

Если из контекста ясно, что подразумеваются операции по модулю n, то индекс n опускается.

Легко видеть, что является абелевой группой, a — коммутативным кольцом с единицей.

Если n — простое число, то (Z_n; +„, -n) является полем.

Рассмотрим — подмножество множества вычетов Z_n, взаимно простых с n.

Числа а и b называются взаимно простыми, если их наибольший общий делитель равен 1.

Можно показать, что (;*n) — абелева группа. Таким образом, для элементов множества существуют обратные по умножению по модулю n.

Функция || называется функцией Эйлера.

Шифрование с открытым ключом.

В настоящее время широкое распространение получили шифры с открытым ключом. Эти шифры не являются симметричными — для зашифровки и расшифровки используются разные ключи. При этом ключ, используемый для зашифровки, является открытым (не секретным) и может быть сообщен всем желающим отправить шифрованное сообщение, а ключ, используемый для расшифровки, является закрытым и хранится в секрете получателем шифрованных сообщений. Даже знание всего зашифрованного сообщения и открытого ключа, с помощью которого оно было зашифровано, не позволяет дешифровать сообщение (без знания закрытого ключа).^[33]

Шифрование с открытым ключом производится следующим образом:

1. Получателем сообщений производится генерация открытого ключа (пара чисел n и e) и закрытого ключа (число d). Для этого

выбираются два простых числа, р и q;

вычисляется первая часть открытого ключа n:=pq;

определяется вторая часть открытого ключа — выбирается небольшое нечётное число е, взаимно простое с числом (р — l)(g — 1) (заметим, что (Р - 1)(9 - 1) = pq( 1 - 1 /р)(1 - l/q) = (n));

определяется закрытый ключ: d: = е^-1 mod (р — 1)(q — 1).

После чего открытый ключ (числа n и е) сообщается всем отправителям сообщений.

2. Отправитель шифрует сообщение (разбивая его, если нужно, на слова S_i длиной менее log₂ n разрядов):

C_i: = mod n,

и отправляет получателю.

3. Получатель расшифровывает сообщение с помощью закрытого ключа d:

P_i: = mod n.

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

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

Цифровая подпись.^[34]

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

Заметим, что операции зашифровки и расшифровки, по существу, одинаковы, и различаются только показателем степени, а потому коммутируют:

М = (M^e)^d mod n = M^ed mod n = M^de mod n = (M^d)^e mod n = M.

Это обстоятельство позволяет применять различные приёмы, известные как цифровая (или электронная) подпись.

Рассмотрим следующую схему взаимодействия корреспондентов X и Y. Отправитель X кодирует сообщение S своим закрытым ключом (С: = mod п) и посылает получателю Y пару (S,C), то есть подписанное сообщение. ПолучательY, получив такое сообщение, кодирует подпись сообщения открытым ключом отправителя X, то есть вычисляет S' : — С^е mod п. Если оказывается, что S = S', то это означает, что (нешифрованное!) сообщение S действительно было отправлено корреспондентом X. Если же S ≠ S', то сообщение было искажено при передаче или фальсифицировано.

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

Можно подписывать и шифрованные сообщения. Для этого отправитель X сначала кодирует своим закрытым ключом сообщение S, получая цифровую подпись С, а затем кодирует полученную пару (S,C) открытым ключом получателя Y. Получив такое сообщение, получатель Y сначала расшифровывает сообщение своим закрытым ключом, а потом убеждается в подлинности полученного сообщения, сравнив его с результатом применения открытого ключа отправителя X к подписи С.

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

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

ЗАКЛЮЧЕНИЕ

Взрывной рост информационных технологий в последние годы, а также пример колоссального влияния таких корпоративных, телекоммуникационных гигантов как «Google», «Apple» и «Huawei» на национальные экономики и мировую экономику в целом, необходимость развития телекоммуникационных сетей пятого поколения и нейронных сетей как фундаментальной базы для создания искусственного интеллекта, что по мнению многих ученых станет толчком для третьей технологической революции, ставят вопрос развитие цифровой экономики в Российской Федерации в один ряд с такими вопросами национальной безопасности как продовольственная и энергетическая независимость.

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

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

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

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

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

БИБЛИОГРАФИЯ

1. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – 288 с.
2. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова – СПб.: Питер, 2011 – 576с.
3. Гомес Ж. Мир Математики. Математика, шпионы и хакеры. Кодирование и криптография / Ж. Гомес. – М.: ООО «Де Агостини», 2014. – 143 с.
4. Иванова Г.С. Технология программирования / Г.С. Иванова – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 320 с.
5. Кудряшов Б.Д. Теория информации / Б.Д. Кудрящов. – Спб.: Питер, 2009 г. – 232 с.
6. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – 432 с.
7. Сэломон Д. Сжатие данных, изображения и звука. / Д. Сэломон. -М.: Техносфера. 2006. - 368 с.
8. Фано Р. Передача информации. Статистическая теория связи. / Р Фано. – М.: Мир. 1965. - 312 с

1. Гомес Ж. Мир Математики. Математика, шпионы и хакеры. Кодирование и криптография / Ж. Гомес. – М.: ООО «Де Агостини», 2014. – с. 31. ↑

2. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – c. 12 ↑

3. Гомес Ж. Мир Математики. Математика, шпионы и хакеры. Кодирование и криптография / Ж. Гомес. – М.: ООО «Де Агостини», 2014. – с. 42. ↑

4. Гомес Ж. Мир Математики. Математика, шпионы и хакеры. Кодирование и криптография / Ж. Гомес. – М.: ООО «Де Агостини», 2014. – с. 52 ↑

5. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – c. 23 ↑

6. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова – СПб.: Питер, 2011 – с. 32 ↑

7. Кудряшов Б.Д. Теория информации / Б.Д. Кудрящов. – Спб.: Питер, 2009 г. – с. 57 ↑

8. Иванова Г.С. Технология программирования / Г.С. Иванова – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – с. 42 ↑

9. Иванова Г.С. Технология программирования / Г.С. Иванова – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – с. 43 ↑

10. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – c. 53 ↑

11. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – c. 53 ↑

12. Кудряшов Б.Д. Теория информации / Б.Д. Кудрящов. – Спб.: Питер, 2009 г. – с. 83 ↑

13. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – c. 57 ↑

14. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – c. 53 ↑

15. Кудряшов Б.Д. Теория информации / Б.Д. Кудрящов. – Спб.: Питер, 2009 г. – с. 121 ↑

16. Иванова Г.С. Технология программирования / Г.С. Иванова – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – с. 122 ↑

17. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова – СПб.: Питер, 2011 – с. 93 ↑

18. Фано Р. Передача информации. Статистическая теория связи. / Р Фано. – М.: Мир. 1965. – с 54 ↑

19. Фано Р. Передача информации. Статистическая теория связи. / Р Фано. – М.: Мир. 1965. – с 57 ↑

20. Кудряшов Б.Д. Теория информации / Б.Д. Кудрящов. – Спб.: Питер, 2009 г. – с. 92 ↑

21. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – с. 231 ↑

22. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – с. 234 ↑

23. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – с. 235 ↑

24. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – с. 126 ↑

25. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – с. 235 ↑

26. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – с. 245 ↑

27. Сэломон Д. Сжатие данных, изображения и звука. / Д. Сэломон. -М.: Техносфера. 2006. - с. 221 ↑

28. Сэломон Д. Сжатие данных, изображения и звука. / Д. Сэломон. -М.: Техносфера. 2006. - с. 262 ↑

29. Гомес Ж. Мир Математики. Математика, шпионы и хакеры. Кодирование и криптография / Ж. Гомес. – М.: ООО «Де Агостини», 2014. – с. 48 ↑

30. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – с. 262 ↑

31. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – с. 267 ↑

32. Новиков Ф.А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. / Ф.А. Новиков. –Спб.: Питер, 2013. – с. 268 ↑

33. Гомес Ж. Мир Математики. Математика, шпионы и хакеры. Кодирование и криптография / Ж. Гомес. – М.: ООО «Де Агостини», 2014. – с. 87 ↑

34. Гомес Ж. Мир Математики. Математика, шпионы и хакеры. Кодирование и криптография / Ж. Гомес. – М.: ООО «Де Агостини», 2014. – с. 101 ↑