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

Далее источник информации полагаем дискретным, выдающим последовательность элементарных сообщений {я,}, каждое из которых выбирается из дискретного ансамбля (алфавита) а, а 2 ,...,й А; к является объемом алфавита источника информации.

Каждое элементарное сообщение содержит определенную информацию как совокупность сведений (в рассматриваемом примере) о состоянии рассматриваемого источника информации. Для количественного определения меры этой информации неважно ее смысловое содержание, а также степень важности этой информации для ее получателя. Заметим, что до получения сообщения у ее получателя всегда имеется неопределенность относительно того, какое сообщение я. из числа всех возможных будет ему передано. Эту неопределенность оценивают с помощью априорной вероятности Р(я,) передачи сообщения я,. Делаем вывод, что объективная количественная мера информации, содержащаяся в элементарном сообщении дискретного источника, устанавливается вероятностью выбора данного сообщения и определяет сс как функцию этой всроятности. Эта же функция характеризует степень неопределенности, имеющуюся у получателя информации относительно состояния дискретного источника. Можно сделать вывод, что степень неопределенности об ожидаемой информации определяет требования к каналам передачи информации.

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

тим, что ^ Р(а :) = 1, так как все я, образуют полную группу собы-

гий), и выбор этих символов осуществляется с помощью некоторой функциональной зависимости J(a,) = Р{а,) = 1, если выбор источником символа априорно определен, J(a,) = а„ a P(a t ,a) - вероятность такого выбора, то количество информации, содержащееся в паре символов, равно сумме количества информации, содержащейся в каждом из символов я, и я, Эго свойство количественной меры информации называют аддитивностью.

Полагаем, что Р(а,) - условная вероятность выбора символа я, после всех предшествующих ему символов, а Р(а, ,я,) - условная вероятность выбора символа я; после я, и всех предшествующих, а, учитывая, что Р(а 1 ,а 1) = Р(а) Р(я,|я у), условие аддитивности можно записать

Введем обозначение Р(а) = Р п Р(ар) = Q и перепишем условие (5.1):

Считаем, что Р, О * 0. Используя выражение (5.2), определим вид функции (р(Р). Осуществив дифференцирование, умножение на Р* 0 и обозначив РО = R, запишем

Отметим, что соотношение (5.3) выполняется при любых R ф О и^^О. Однако это требование приводит к постоянству правой и левой частей (5.3): Pq>"(P)= Ар"(/?) - к - const. Тогда приходим к уравнению Рц>"(Р) = К и после интегрирования получаем

Учтем, что и перепишем

Следовательно, при выполнении двух условий о свойствах J(a,) выявилось, что вид функциональной зависимости J(a,) от вероятности выбора символа a t с точностью до постоянного коэффициента К однозначно определяется

Коэффициент К влияет только на масштаб и определяет систему единиц измерения количества информации. Так как 1п[Р] Ф 0, то имеет смысл выбрать К Ос тем, чтобы мера количества информации J(a) была положительной.

Приняв К= -1, запишем

Отсюда следует, что единица количества информации равна информации о том, что наступило событие, вероятность которого равна Me. Такая единица количества информации называется натуральной единицей. Чаще полагают, что К = -, тогда

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

где логарифм может быть с произвольным основанием.

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

Количественная мера информации содержащейся в элементарном сообщении а (, не дает представления о среднем количестве информации J(A ), выдаваемом источником при выборе одного элементарного сообщения а г

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

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

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

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

Энтропия будет максимальной в случае равенства априорных вероятностей всех возможных символов К , т.е. Р(а {) = 1 /К, тогда

Если источник независимо выбирает двоичные символы с вероятностями Р, = Р(а х) и Р 2 = 1 - Р, то энтропия на один символ будет

На рис. 16.1 показана зависимость энтропии двоичного источника от априорной вероятности выбора из двух двоичных символов, из этого рисунка также видно, что энтропия максимальна при Я, = Р 2 = 0,5

1 о 1 двед - и в двоичных единицах log 2 2 = 1-

Рис. 5.1. Зависимость энтропии при К = 2 от вероятности выбора одного из них

Энтропия источников с равновероятным выбором символов, но с различными объемами алфавитов К, логарифмически увеличивается с ростом К.

Если вероятность выбора символов различна, то падает энтропия источника И(А) относительно возможного максимума Н(А) пш = logК.

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

Введя обозначение Р(аа") для условной вероятности выбора символа а,(/ = 1, 2, К) при условии, что ранее выбран символ ajij =1,2,К) и опуская преобразования, без доказательства запишем

что доказывает неравенство (5.13).

Равенство в (5.13) или (5.14) достигается в случае, когда

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

Интересно, что энтропия текста на русском языке составляет 1,5 двоичных единиц на символ. В то же время при том же алфавите К= 32 с условием независимых и равновероятных символов Н(А) тп = 5 двоичных единиц на символ. Таким образом, наличие внутренних связей уменьшило энтропию приблизительно в 3,3 раза.

Важной характеристикой дискретного источника является его избыточность р и:

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

Для передачи некоторого объема информации от источника, не имеющего корреляционных связей между символами, при равной вероятности всех символов требуется минимально возможное количество передаваемых символов /7 min: /г 0 (/7 0 Я(Л тах)). Для передачи того же объема информации от источника с энтропией (символы взаимосвязаны и неравновероятны) потребуется среднее количество симво- лов п = n„H(A) m JH(A).

Дискретный источник характеризуется также производительностью, определяющейся числом символов за единицу времени v H:

Если производительность И(А) определять в двоичных единицах, а время в секундах, то Н"(А) - это число двоичных единиц в секунду. Для дискретных источников, выдающих стационарные последовательности символов достаточно большой длины /?, вводят понятия: типичные и нетипичные последовательности символов источника, на которые можно разбить все последовательности длиной п. Все типичные последовательности N lMl (A) источника при п -»оо имеют примерно одинаковую вероятность появления

Суммарная вероятность появления всех нетипичных последовательностей при этом стремится к нулю. В соответствии с равенством (5.11), полагая, что вероятность типичных последовательностей /N rm (A), энтропия источника равна logN TIin (,4) и тогда

Рассмотрим количество и скорость передачи информации по дискретному каналу с шумами. Раньше рассматривалась информация, выдаваемая дискретным источником в виде последовательности символов {я,}.

Теперь предположим, что информация источника кодируется и представляет последовательность кодовых символов {Ь, (/ = 1,2,..т - основание кода), согласовывается с дискретным каналом передачи информации, на выходе которого появляется последовательность сим-

Предполагаем, что операция кодирования взаимно-однозначная - по последовательности символов {Ь,} можно однозначно восстановить последовательность {я,}, т.е. по кодовым символам можно восстановить информацию источника полностью.

Однако если рассмотреть символы выхода |?. j и символы входа {/>,}, то вследствие наличия в канале передачи информации помех, восстановление невозможно. Энтропия выходной последовательности //(/?)

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

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

Оценим потери информации в канале с шумами и количество информации, переданной по каналу с шумами. Считаем, что символ передан правильно, если при переданном символе 6, принят

символ bj с тем же номером (/ = j). Тогда для идеального канала без шумов запишем:

По символу bj -на выходе канала вследствие неравенств (5.21)

неопределенность неизбежна. Можно считать, что информация в символе b i не передана полностью и часть ее потеряна в канале из-за воздействия помех. Основываясь на понятии количественной меры информации, будем считать, что численное выражение неопределенности, возникающей на выходе канала после приема символа ft ; :

и оно определяет количество потерянной информации в канале в процессе передачи.

Зафиксировав ft . и усреднив (5.22) по всем возможным символам, получаем сумму

определяющую количество теряемой в канале информации при передаче по каналу без памяти элементарного символа при приеме символа bj(t).

При усреднении суммы (5.23) по всем ft получаем величину Z?), которую обозначаем через н(в/В- Она определяет количество информации, теряемой при передаче одного символа по каналу без памяти:

где P^bjbjj - совместная вероятность события, что при передаче

символа Ь. он примет символ b t .

Н [в/ зависит от характеристик источника информации на

входе канала В и от вероятностных характеристик канала связи. По Шеннону в статистической теории связи н(в/в называют ненадежностью канала.

Условная энтропия НВ/ В , энтропия дискретного источника

на входе канала Н(В) и энтропия И ^В ) на его выходе не могут быть

отрицательными. В канале без помех ненадежность канала

н(в/в = 0. В соответствии с (5.20) отметим, что Н^в/В^

а равенство имеет место только при статистической независимости входа и выхода канала:

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

Как и ранее, для типичных последовательностей можно запи

сать, что при отсутствии помех его ненадежность

Под переданной в среднем по каналу информацией J[ b/на один символ понимаем разность между количеством информации на входе канала J(B) и информацией, потерянной в канале /?).

Если источник информации и канал без памяти, то

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

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

Как правило, учитывается наиболее распространенный вид помех - аддитивные шумы N(t); сигнал на выходе канала имеет вид:

Для дискретных сигналов эквивалентный шум, следуя из (5.28), имеет дискретную структуру. Шум представляет собой дискретную случайную последовательность, похожую на последовательности входящего и выходящего сигналов. Обозначим символы алфавита аддитивного шума в дискретном канале через Ц1 = 0, 1,2, т - 1). Условные вероятности перехода в таком канале

Так как И {^В /?) И (В) то, следовательно, информация выходной последовательности дискретного канала #(/) относительно входной B(t) или наоборот И (В)- Н^в/в} (5).

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

Если на вход канала поступает в среднем х к символов за одну секунду, то можно определить среднюю скорость передачи информации по каналу с шумами:

где Н(В) = V k J(B,B^ - производительность источника на входе канала; н(в/в) = У к н(в,в) ~ ненадежность канала в единицу времени; Н (B) = V k H^B^ - производительность источника, образованного выходом канала (выдающего часть полезной и часть ложной информации); Н^в/В^ = У к 1/(в/в) - количество ложной информации,

создаваемой помехой в канале в единицу времени.

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

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

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

где максимум берегся по возможным источникам входа В при заданном V k и объеме алфавита символов входа т.

Исходя из определения пропускной способности дискретного канала запишем

Заметим, что С = 0 при независимом входе и выходе (высок уровень помех в канале) и соответственно

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

Для двоичного симметричного канала без памяти

Рис. 5.2.

График зависимости пропускной способности двоичного канала от параметра р представлен на рис. 5.2. При р = 1/2 пропускная способность канала С = 0, условная энтропия

//(/?//?) = 1. Практический интерес

график представляет при 0

Основная теорема Шеннона по оптимальному кодированию связана с понятием пропускной способности. Ее формулировка для дискретного канала следующая: если производительность источника сообщений Н[А) меньше пропускной способности канала С:

го существует способ оптимального кодирования и декодирования, при кагором вероятность ошибки или ненадежность канала н[а!A j может быть сколь угодно мала. Если

го таких способов не существует.

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

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

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

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

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

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

В теории кодирования существует ряд направлений:

• статическое или эффективное кодирование;
• помехоустойчивое кодирование;
• корректирующие коды;
• циклические коды;
• арифметические коды.

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

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

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

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

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

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

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

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

Кодирование текста

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

Однако, ограниченный набор из 256 кодов символов сегодня уже не удовлетворяет возросшие потребности международного общения. Все большее распространение получает универсальная система 16-разрядного кодирования символов UNICODE .

Мощность алфавита в системе кодирования UNICODE составляет 216=65 536 разных кодов, из которых 63 484 кода соответствуют символам большинства алфавитов, а оставшиеся 2048 кодов разделены пополам и образуют таблицу размером 1024 столбцов х 1024 строк. В этой таблице более миллиона ячеек, в которых можно разместить еще более миллиона различных символов. Это символы «мертвых» языков, а также символы, не имеющие лексического содержания, указатели, знаки и т.п. Для записи этих дополнительных символов необходима пара 16-разрядных слов (16 разрядов для номера строки и 16 разрядов для номера столбца).

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

Кодирование изображений

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

Черно-белые изображения принято представлять в градациях серого цвета, для этого используется модель GreyScale . Если яркость точки кодируется одним байтом, можно использовать 256 различных серых тонов. Такая точность согласуется с восприимчивостью человеческого глаза и возможностями полиграфической техники.

При кодировании цветных изображений применяют принцип декомпозиции цвета на составляющие, для этого используют модель RGB . Цветное изображение на экране получается путем смешивания трех базовых цветов: красного (Red, R), синего (Blue, B) и зеленого (Green, G).

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

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

Код цвета пикселя содержит информацию о доле каждого базового цвета.

схема цветообразования

Если все три составляющих имеют одинаковую интенсивность (яркость), то из их сочетаний можно получить 8 различных цветов (23):

Формирование цветов при глубине цвета 24 бита:

Чем больше глубина цвета, тем шире диапазон доступных цветов и тем точнее их представление в оцифрованном изображении. Пиксель с битовой глубиной, равной единице, имеет лишь 2 (в первой степени) возможных состояния — два цвета: черный или белый. Пиксель с битовой глубиной в 8 единиц имеет 28 или 256 возможных цветовых значений. Пиксель же с битовой глубиной в 24 единицы имеет 224 степени) или 16,7 миллионов возможных значений. Считается, что 24-битные изображения, содержащие 16,7 миллионов цветов, достаточно точно передают краски окружающего нас мира. Как правило, битовое разрешение задается в диапазоне от 1 до 48 бит/пиксель.

При печати на бумаге используется несколько иная цветовая модел: если монитор испускал свет, оттенок получался в результате сложения цветов, то краски - поглощают свет, цвета вычитаются. Поэтому в качестве основных используют голубую (Cyan, C), пурпурную (Magenta, M) и желтую (Yellow, Y) краски. Кроме того, из-за не идеальности красителей, к ним обычно добавляют четвертую -- черную (black, K). Для хранения информации о каждой краске и в этом случае чаще всего используется 1 байт. Такая система кодирования носит название CMYK .

Более грубое представление цвета использует меньшее число разрядов. Например, кодирование цветной графики 16-разрядными числами носит название High Color . В этом случае каждому цвету отводят пять разрядов.

Кодирование звука и видео

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

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

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

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

Теория кодирования. Виды кодирования Основные понятия теории кодирования Ранее средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения, но с появлением компьютеров ситуация радикально изменилась. Кодирование буквально пронизывает информационные технологии и является центральным вопросом при решении самых разных (практически всех) задач программирования: ۞ представление данных произвольной природы (например, чисел, текста, графики) в памяти компьютера; ۞ защита информации от несанкционированного доступа; ۞ обеспечение помехоустойчивости при передаче данных по каналам связи; ۞ сжатие информации в базах данных. Теория кодирования ­ это раздел теории информации, изучающий способы отождествление сообщений с отображающими их сигналами. Задача: Согласовать источник информации с каналом связи. Объект: Дискретная или непрерывная информация, поступающая к потребителю через источник информации. Кодирование – это преобразования информации в формулу удобную для передачи по определенному каналу связи. Примером кодирования в математике является метод координат, введенный Декартом, который дает возможность изучать геометрические объекты через их аналитическое выражение в виде чисел, букв и их комбинаций - формул. Понятие кодирование означает преобразование информации в форму, удобную для передачи по определенному каналу связи. Декодирование – восстановление принятого сообщения из­за кодированного вида в вид доступный для потребителя.

Тема 5.2. Алфавитное кодирование В общем случае задачу кодирования можно представить следующим образом. Пусть заданы два алфавита А и В, состоящие из конечного числа символов: и. Элементы алфавита называются буквами. Упорядоченный набор в алфавите А назовем словом,где обозначается п =l()=| |. , число п показывает количество букв в слове и называется длиной слова, Пустое слово обозначается: Для слова буква a1, называется началом, или префиксом, слова буква an - окончанием, или постфиксом, слова. , а Слова можно соединять. Для этого префикс второго слова должен следовать сразу за постфиксом первого, при этом в новом слове они, естественно, утрачивают свой статус, если только одно из слов не было пустым. Соединение слов и обозначается, соединение п одинаковых слов обозначается, причем. Множество всех непустых слов алфавита А обозначим А*: Множество А называют алфавитом сообщений, а множество В - кодирующим алфавитом. Множество слов, составленных в алфавите В, обозначим В*.

Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово назовем кодом слова. Кодированием называют универсальный способ отображения информации при ее хранении, передаче и обработке в виде системы соответствий между элементами сообщений и сигналами, при помощи которых эти элементы можно зафиксировать. Таким образом, код - правило однозначного преобразования (т.е. функция) сообщения из одной символической формы представления (исходного алфавита А) в другую (объектный алфавит В), обычно без каких­либо потерь информации. Процесс преобразования F: А* В*→ слов исходного алфавита А в алфавит В называется кодированием информации. Процесс обратного преобразования слова называется декодированием. Таким образом, декодирование - функция, обратная F, т.е. F­1. в слово Так как для любого кодирования должна выполняться операция декодирования, то отображение должно быть обратимым (биекция). Если |B|= m, то F называется m­ичным кодированием, наиболее распространенный случай В = {0, 1}­ двоичное кодирование. Именно этот случай и рассматривается в дальнейшем. Если все кодовые слова имеют одинаковую длину, то код на­ зывается равномерным, или блочным. Алфавитное (или побуквенное), кодирование можно задать таблицей кодов. Кодом или кодирующей функцией, будет служить некоторая подстановка. Тогда, где, . Такое побуквенное кодирование обозначается называется множеством элементарных кодов. Алфавитное кодирование можно использовать для любого множества сообщений. Таким образом, алфавитное кодирование является самым простым, и его всегда можно ввести на непустых алфавитах. . Множество кодов букв

ПРИМЕР Пусть заданы алфавиты А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} В = {0, 1}. Тогда таблица кодирования может быть подстановкой: . Это двоично­десятичное кодирование, оно является взаимнооднозначным и потому допускает декодирование. Однако схема не является взаимно­однозначной. Например, набор из шести единиц 111111 может соответствовать как слову 333, так и 77, а также 111111, 137, 3311 или 7111 плюс любая перестановка. Схема алфавитного кодирования называется префиксной, если элементарный код одной буквы не является префиксом элементарного кода другой буквы. Схема алфавитного кодирования называется разделимой, если любое слово, составлен­ ное из элементарных кодов, разлагается на элементарные коды единственным образом. Алфавитное кодирование с разделимой схемой допускает декодирование. Можно доказать, что префиксная схема является разделимой. Для того чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли соотношению, известному какнеравенство Макмиллана. Неравенство Макмиллана Если схема алфавитного кодирования

разделима, то справедливо неравенство ПРИМЕР Схема алфавитного кодирования А={ а, b} и В={0, 1}, является разделимой, т. к. , и, значит, выполняется неравенство Макмиллана Данная схема префиксной не является, т.к. элементарный код буквы а является префиксом элементарного кода буквы b. Тема 5.3. Кодирование с минимальной избыточностью На практике важно, чтобы коды сообщений имели по возможности наименьшую длину. Алфавитное кодирование пригодно для любых сообщений, если же про множество всех слов алфавита А ничего не известно, то точно сформулировать задачу оптимизации трудно. Однако на практике часто доступна дополнительная информация. Например, для сообщений, представленных на естественном языке, такой дополнительной информацией может быть распределение вероятности появления букв в сообщении. Тогда задача построения оптимального кода приобретает точную математическую формулировку и строгое решение.

Пусть задана некоторая разделимая схема алфавитного кодирования. Тогда любая схема, где упорядоченный набор есть перестановка упорядоченного, также будет разделимой. В таком случае, если длины элементарных набора кодов равны, то их перестановка в схеме не влияет на длину закодированного сообщения. В том случае, если длины элементарных кодов различны, то длина кода сообщения напрямую зависит и от того, какие элементарные коды каким буквам поставлены в соответствие, и от того, каков состав букв в сообщении. Если заданы конкретное сообщение и конкретная схема кодирования, то можно подобрать такую перестановку кодов, при которой длина кода сообщения будет минимальной. Алгоритм назначения элементарных кодов, при котором длина кода фиксированного сообщения S будет минимальна при фиксированной схеме: ۞ отсортировать буквы в порядке убывания количества вхождений; ۞ отсортировать элементарные коды в порядке возрастания длины; ۞ поставить коды в соответствие буквам в установленном порядке. Пусть задан алфавит и вероятности появления букв в сообщении:

Где рi - вероятность появления буквы ai, причем буквы с нулевой вероятностью появления в сообщении исключены и буквы упорядочены по убыванию вероятности их появления Для разделимой схемы алфавитного кодирования при распределении вероятностей Р существует так называемая средняя цена, или длина кодирования, - это математическое ожидание длины закодированного сообщения, которая обозначается и определяется как ПРИМЕР. Для разделимой схемы алфавитного кодирования А={а,b}, В={0,1}, при распределении вероятностей цена кодирования составляет а при распределении вероятностей цена кодирования составляет

Тема 5.4. Кодирование методом Хаффмана Этот алгоритм был изобретен в 1952 году Дэвидом Хаффманом. Тема 5.5. Арифметическое кодирование Как и в алгоритме Хаффмана, все начинается с таблицы элементов и соответствующих вероятностей. Допустим, входной алфавит состоит всего из трех элементов: a1, a2 и a3, и при этом P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 Предположим также, что нам надо закодировать последовательность a1, a1, a2, a3 . Разобьем полуинтервал , где р ­ некотороефиксированное число, 0<р<(r­1)/2r, а "мощностная" граница где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист

ра сдвига и одного мажоритарного элемента и исправляющий одну ошибку, имеетпорядок (ср. с (2)). В качестве математич. модели кодера и декодера обычно рассматривают с хемы изфункциональных элементов и под сложностью понимают число элементов в схеме. Для известных классовкодов с исправлением ошибок проведено исследование возможных а лгоритмов К. и д. и получены верхниеграницы сложности кодера и декодера. Найдены такж е нек­рые соотношения между скоростью передачикодирования, помехоустойчивостью код ирования и сложностью декодера (см. ). Еще одно направление исследований в теории кодирования связано с тем, что многие резул ьтаты (напр.,теорема Шеннона и граница (3)) не являются "конструктивными", а представл яют собой теоремысуществования бесконечных последовательностей {К п} кодов В связи с этим предпринимаютсяусилия, чтобы доказать эти результаты в классе таких последовательностей {К п} кодов, для к­рых существуетмашина Тьюринга, распознаю щая принадлежность произвольного слова длины lмножеству завремя, имеющее м едленный порядок роста относительно l(напр., llog l). Нек­рые новые конструкции и методы получения границ, разработанные в теории кодирова ния, привели ксущественному продвижению в вопросах, на первый взгляд весьма далеких о т традиционных задач теориикодирования. Здесь следует указать на использование максим ального кода с исправлением одной ошибки васимптотически оптимальном методе реализа ции функций алгебры логики контактными схемами;напринципиальное улучшение верхне й границы для плотности упаковки re­мерного евклидова пространстваравными шарами; на использование неравенства (1) при оценке сложности реализации формулами одногокласса функций алгебры логики. Идеи и результаты теории кодирования находят свое дальнейшее развитие взадачах синтеза самокорректирующихся схем и надежных схем из ненадежных эл ементов. Лит.: Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963; Берлекэмп Э.,Алгебраическая теория кодирования, пер. с англ., М., 1971; Питерсон У., Уэлдон Э., Коды, исправляющиеошибки, пер. с англ., 2 изд., М., 1976; Дискретная математика и математические вопросы кибернетики, т.1,М., 1974, раздел 5; Бассалыго Л. А., Зяблов В. В., Пинскер М. С, "Пробл. передачи информации", 1977, т.13, № 3, с. 5­17; [В] Сидельников В. М., "Матем. сб.", 1974, т. 95, в. 1, с. 148 ­ 58. В. И. Левенштейн.

Математическая энциклопедия. - М.: Советская энциклопедия. И. М. Виноградов. 1977-1985.  КОДИРОВАНИЕ АЛФАВИТНОЕ  КОЕВКЛИДОВО ПРОСТРАНСТВО См. также в других словарях:  ДЕКОДИРОВАНИЕ - см. Кодирование и декодирование … Математическая энциклопедия  Кодирование звуковой информации - Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. В основе кодирования звука с использованием ПК лежит процесс преобразования колебаний воздуха в колебания электрическог … Википедия  КОДИРОВАНИЕ - (от франц. code – свод законов, правил) – отображение (преобразование) нек рых объектов (событий, состояний) в систему конструктивных объектов (называемых кодовыми образами), совершаемое по определ. правилам, совокупность к рых наз. шифром К.,… … Философская энциклопедия  КОДИРОВАНИЕ ИНФОРМАЦИИ - установление соответствия между элементами сообщения и сигналами, при помощи к рых эти элементы могут быть зафиксированы. Пусть В, множество элементов сообщения, А алфавит с символами, Пусть конечная последовательность символов наз. словом в… … Физическая энциклопедия  КОДИРОВАНИЕ ОПТИМАЛЬНОЕ - (в инженерной психологии) (англ. optimal coding) создание кодов, обеспечивающих максимальную скорость и надежность приема и переработки информации об объекте управления человеком оператором (см. Прием информации, Декодирование). Проблема К. о.… … Большая психологическая энциклопедия  ДЕКОДИРОВАНИЕ (в инженерной психологии) - (англ. decoding) заключительная операция процесса приема информации человеком оператором, состоящая в перешифровке параметров, характеризующих состояние объекта управления, и в переводе их в образ управляемого объекта (см. Кодирование… … Большая психологическая энциклопедия

 Декодирование - восстановление сообщения, закодированного переданными и принятыми сигналами (см. Кодирование) … Экономико­ математический словарь  КОДИРОВАНИЕ - КОДИРОВАНИЕ. Один из этапов порождения речи, в то время как «декодирование» – прием и интерпретация, процесс понимания речевого сообщения. См. психолингвистика … Новый словарь методических терминов и понятий (теория и практика обучения языкам)  КОДИРОВАНИЕ - (англ. coding). 1. Преобразование сигнала из одной энергетической формы в др. 2. Преобразование одной системы сигналов или знаков в др., что часто называется также «перекодированием», «сменой кода» (для речи «перевод»). 3. К. (мнемическое)… … Большая психологическая энциклопедия  Декодирование - Эта статья о коде в теории информации, другие значения этого слова см. в код (значения). Код правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков) (или сигналов). Кодом также называется… … Оптимальное кодирование Одно и то же сообщение можно закодировать различными способами. Оптимально закодированным будем считать такой код, при котором на передачу сообщений затрачивается минимальное время. Если на передачу каждого элементарного символа (0 или 1) тратиться одно и то же время, то оптимальным будет такой код, который будет иметь минимально возможную длину. Пример 1. Пусть имеется случайная величина X(x1,x2,x3,x4,x5,x6,x7,x8), имеющая восемь состояний с распределением вероятностей Для кодирования алфавита из восьми букв без учета вероятностей равномерным двоичным кодом нам понадобятся три символа: Это 000, 001, 010, 011, 100, 101, 110, 111 Чтобы ответить, хорош этот код или нет, необходимо сравнить его с оптимальным значением, то есть определить энтропию

Определив избыточность L по формуле L=1­H/H0=1­2,75/3=0,084, видим, что возможно сокращение длины кода на 8,4%. Возникает вопрос: возможно ли составить код, в котором на одну букву будет, в среднем приходится меньше элементарных символов. Такие коды существуют. Это коды Шеннона­Фано и Хаффмана. Принцип построения оптимальных кодов: 1. Каждый элементарный символ должен переносить максимальное количество информации, для этого необходимо, чтобы элементарные символы (0 и 1) в закодированном тексте встречались в среднем одинаково часто. Энтропия в этом случае будет максимальной. 2. Необходимо буквам первичного алфавита, имеющим большую вероятность, присваивать более короткие кодовые слова вторичного алфавита.

04.04.2006 Леонид Черняк Рубрика:Технологии

«Открытые системы» Создание компьютеров было бы невозможно, если одновременно с?их появлением не была бы создана теория кодирования сигналов Теория кодирования?- одна из тех областей математики, которые заметно повлияли на развитие компьютинга.

«Открытые системы»

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

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

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

Первым теоретическое решение проблемы передачи данных по зашумленным каналам предложил Клод Шеннон, основоположник статистической теории информации. Шеннон был звездой своего времени, он входил в академическую элиту США. Будучи аспирантом Ванневара Буша, в 1940 году он получил премию имени Нобеля (не путать с Нобелевской премией!), присуждаемую ученым, не достигшим 30 лет. Работая в Bell Labs, Шеннон написал работу «Математическая теория передачи сообщений» (1948), где показал, что если пропускная способность канала выше энтропии источника сообщений, то сообщение можно закодировать так, что оно будет передано без излишних задержек. Это умозаключение содержится в одной из доказанных Шенноном теорем, ее смысл сводится к тому, что при наличии канала с достаточной пропускной способностью сообщение может быть передано с некоторыми временными задержками. Кроме того, он показал теоретическую возможность достоверной передачи при наличии шума в канале. Формулу C = W log ((P+N)/N), высеченную на скромном памятнике Шеннону, установленном в его родном городе в штате Мичиган, сравнивают по значению с формулой Альберта Эйнштейна E = mc 2 .

Труды Шеннона дали пищу для множества дальнейших исследований в области теории информации, но практического инженерного приложения они не имели. Переход от теории к практике стал возможен благодаря усилиям Ричарда Хэмминга, коллеги Шеннона по Bell Labs, получившего известность за открытие класса кодов, которые так и стали называть «кодами Хэмминга». Существует легенда, что к изобретению своих кодов Хэмминга подтолкнуло неудобство в работе с перфокартами на релейной счетной машине Bell Model V в середине 40-х годов. Ему давали время для работы на машине в выходные дни, когда не было операторов, и ему самому приходилось возиться с вводом. Как бы то ни было, но Хэмминг предложил коды, способные корректировать ошибки в каналах связи, в том числе и в магистралях передачи данных в компьютерах, прежде всего между процессором и памятью. Коды Хэмминга стали свидетельством того, как можно практически реализовать возможности, на которые указывают теоремы Шеннона.

Хэмминг опубликовал свою статью в 1950 году, хотя во внутренних отчетах его теория кодирования датируется 1947 годом. Поэтому некоторые считают, что отцом теории кодирования следует считать Хэмминга, а не Шеннона. Впрочем, в истории техники бесполезно искать первого.

Достоверно только то, что именно Хэмминг первым предложил «коды с исправлением ошибок» (Error-Correcting Code, ECC). Современные модификации этих кодов используются во всех системах хранения данных и для обмена между процессором и оперативной памятью. Один из их вариантов, коды Рида-Соломона применяются в компакт-дисках, позволяя воспроизводить записи без скрипов и шумов, которые могли бы вызвать царапины и пылинки. Существует множество версий кодов, построенных «по мотивам» Хэмминга, они различаются алгоритмами кодирования и количеством проверочных битов. Особое значение подобные коды приобрели в связи с развитием дальней космической связи с межпланетными станциями, например, существуют коды Рида-Мюллера, где на семь информационных битов приходится 32 контрольных, или на шесть - 26.

Среди новейших кодов ECC следует назвать коды LDPC (Low-Density Parity-check Code). Вообще-то они известны лет тридцать, но особый интерес к ним обнаружился именно в последние годы, когда стало развиваться телевидение высокой четкости. Коды LDPC не обладают 100-процентной достоверностью, но вероятность ошибки может быть доведена до желаемой, и при этом с максимальной полнотой используется пропускная способность канала. К ним близки «турбокоды» (Turbo Code), они эффективны при работе с объектами, находящимися в условиях далекого космоса и ограниченной пропускной способности канала.

В историю теории кодирования прочно вписано имя Владимира Александровича Котельникова. В 1933 году в «Материалах по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи» он опубликовал работу «О пропускной способности?эфира? и?проволоки?». Имя Котельникова на правах равного входит в название одной из важнейших теорем теории кодирования. Этой теоремой определяются условия, при которых переданный сигнал может быть восстановлен без потери информации.

Эту теорему называют по-разному, в том числе «теоремой WKS» (аббревиатура WKS взята от Whittaker, Kotelnikov, Shannon). В некоторых источниках используют и Nyquist-Shannon sampling theorem, и Whittaker-Shannon sampling theorem, а в отечественных вузовских учебниках чаще всего встречается просто «теорема Котельникова». На самом же деле теорема имеет более долгую историю. Ее первую часть в 1897 году доказал французский математик Эмиль Борель. Свой вклад в 1915 году внес Эдмунд Уиттекер. В 1920 году японец Кинносуки Огура опубликовал поправки к исследованиям Уиттекера, а в 1928 году американец Гарри Найквист уточнил принципы оцифровки и восстановления аналогового сигнала.

Клод Шеннон (1916 - 2001) со школьных лет проявлял равный интерес к математике и электротехнике. В 1932 году он поступил в Университет штата Мичиган, в 1936-м - в Массачусетский технологический институт, который закончил в 1940 году, получив две степени - магистра по электротехнике и доктора в области математики. В 1941 году Шеннон поступил на работу в Bell Laboratories. Здесь он начал развивать идеи, которые впоследствии вылились в теорию информации. В 1948-м Шеннон опубликовал статью «Математическая теория связи», где были сформулированы базовые идеи ученого, в частности, определение количества информации через энтропию, а также предложил единицу информации, определяющую выбор из двух равновероятных вариантов, то есть то, что впоследствии назвали битом. В 1957-1961 годах Шеннон опубликовал работы, где доказывалась теорема о пропускной способности зашумленных каналов связи, которая теперь носит его имя. В 1957 году Шеннон стал профессором Массачусетского технологического института, откуда ушел на пенсию спустя 21 год. На «заслуженном отдыхе» Шеннон полностью отдался своему давнему увлечению жонглированием. Он построил несколько жонглирующих машин и даже создал общую теорию жонглирования.

Ричард Хэмминг (1915 - 1998) начал свое образование в Чикагском университете, где в 1937 году получил степень бакалавра. В 1939 году он получил степень магистра в Университете Небраски, а степень доктора по математике - в Университете Иллинойса. В 1945 году Хэмминг начал работать в рамках Манхэттенского проекта - масштабной государственной научно-исследовательской работы по созданию атомной бомбы. В 1946 году Хэмминг поступил на работу в Bell Telephone Laboratories, где работал в том числе с Клодом Шенноном. В 1976 году Хэмминг получил кафедру в военно-морской аспирантуре в Монтерей в Калифорнии.

Труд, сделавший его знаменитым, фундаментальное исследование кодов обнаружения и исправления ошибок, Хэмминг опубликовал в 1950 году. В 1956 году он принимал участие в работе над одним из ранних мэйнфреймов IBM 650. Его работы заложили основу языка программирования, который позднее эволюционировал в языки программирования высокого уровня. В знак признания заслуг Хэмминга в области информатики институт IEEE учредил медаль за выдающиеся заслуги в развитии информатики и теории систем, которую назвал его именем.

Владимир Котельников (1908 - 2005) в 1926 году поступил на Электротехнический факультет Московского высшего технического училища имени Н. Э. Баумана (МВТУ), но стал выпускником Московского энергетического института (МЭИ), который выделился из МВТУ как самостоятельный институт. Во время обучения в аспирантуре (1931-1933) Котельников математически точно сформулировал и доказал «теорему отсчетов», которая впоследствии была названа его именем. После окончания аспирантуры в 1933 году Котельников, оставаясь преподавать в МЭИ, поступил на работу в Центральный научно-исследовательский институт связи (ЦНИИС). В 1941 году В. А. Котельников сформулировал четкое положение о том, каким требованиям должна удовлетворять математически недешифруемая система и дано доказательство невозможности ее дешифровки. В 1944 году Котельников занял должность профессора, декана радиотехнического факультета МЭИ, где проработал до 1980 года. В 1953 году в возрасте 45 лет Котельников был избран сразу действительным членом Академии наук СССР. С 1968 по 1990 год В. А. Котельников был также профессором, заведующим кафедрой Московского физико-технического института.

Рождение теории кодирования

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

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

Широко известны способы числового кодирования геометрических объектов и их положения в пространстве: декартовы координаты и полярные координаты. И эти способы кодирования отличаются присущими им специфическими особенностями.

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

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

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

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

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

– сжатие информации.

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

Кодирование может быть числовым (цифровым) и нечисловым, в зависимости от вида, в котором представлены кодовые символы: числа в какой-либо системе счисления или иные какие-то объекты или знаки соответственно.

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

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

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

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

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

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

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

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

M = a·n. (2.1)

Наибольшее количество различных чисел, которое может быть записано в этом устройстве N :

N = a n .

Прологарифмировав это выражение и выразив из него n получим:

n = ln N / ln a.

Преобразовав выражение (2.1) к виду

M = a ∙ ln N / ln a (2.2)

можно определить, при каком основании логарифмов a количество элементов M будет минимальным при заданном N . Продифференцировав по a функцию M = f(a) и приравняв её производную к нулю, получим:

Очевидно, что для любого конечного a

ln N / ln 2 a ≠ 0

и, следовательно,

ln a - 1 = 0,

откуда a = e ≈ 2,7.

Так как основание системы счисления может быть только целым числом, то а выбирают равным 2 или 3. Для примера зададимся максимальной емкостью устройства хранения N =10 6 чисел. Тогда при различных основаниях систем счисления (а )количество элементов (M )в таком устройстве хранения будет, в соответствии с выражением (2.2), следующие (Таблица 2.1):

Таблица 2.1.

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