WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |
Факультет компьютерных наук Кафедра информационных систем А.В. Сычев Информатика.

Кодирование и передача дискретных сообщений.

Учебное пособие для I курса факультета компьютерных наук Воронеж – 2002 2 УДК 681.3 Сычев А.В. Информатика. Кодирование и передача дискретных собщений. – Воронеж: ВГУ, 2002.

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

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

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

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

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

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

1.1. Знаки, наборы знаков, алфавиты Языковые сообщения в письменной форме строят обычно, записывая знаки письма (графемы) друг за другом. Хотя длинные сообщения могут размещаться на многих строчках и страницах, это разбиение не имеет, вообще говоря, никакого значения; оно не несёт важной информации. По существу такие сообщения являются последовательностями знаков. Это оказывается справедливым и для устных языковых сообщений, если разложить устный текст на элементарные составные части, так называемые фонемы, и под знаками понимать фонемы.

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

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

Знак - это элемент некоторого конечного множества отличимых друг от друга „вещей", набора знаков.

Набор знаков, в котором определён (линейный) порядок знаков, называется алфавитом.

Вот некоторые примеры алфавитов (порядок в них — это порядок перечисления):

а) алфавит десятичных цифр {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

b) алфавит заглавных латинских букв {A,B,C,D,E,F,G,H,I,J,K,L,M,N,0,P,Q,R,S, T,U,V,W,X,Y,Z};

с) алфавит заглавных кириллических букв {А,Б,В,Г,Д,Е,Ж,З.И,Й,К,Л,М,Н,0,П,Р,С,Т, У,Ф,Х,Ц,Ч,Ш,Щ,Ъ,Ы,Ь,Э,Ю,Я};

d) алфавит японской катаканы e) алфавит международного кода семафорной сигнализации ж) набор знаков азбуки Морзе 1.2. Коды и кодирования Если N - предложение некоторого естественного языка, то N можно рассматривать как последовательность знаков, по крайней мере, тремя разными способами.

Прежде всего, N представляет собой последовательность букв, цифр, знаков препинания и т. д.; далее, N — это последовательность слов, которые в другом контексте могут сами рассматриваться как знаки; наконец, и всё предложение целиком можно рассматривать как один знак.

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

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

На более высоком уровне каждое слово можно снова рассматривать как знак, при этом соответствующий набор знаков будет, вообще говоря, шире первоначального. Обратно, данный набор знаков можно получить с помощью составления слов, исходя из некоторого набора с меньшим числом знаков, в частности из двоичного набора знаков. Некоторые из перечисленных выше наборов получены с помощью словообразования „над" конкретными двоичными наборами знаков или, абстрактно, над набором {1, 0}.



Слова над двоичным набором знаков называются двоичными словами. Они не обязаны иметь постоянную длину (см. азбуку Морзе), если это всё же так, то говорят об n-разрядных двоичных знаках и n-разрядных двоичных кодах.

Дадим теперь точное определение:

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

Помимо основного значения слова „code" - «кодекс», «свод законов» (гражданский кодекс, кодекс Наполеона) - начиная с середины 19-го в. оно означало книгу, в которой словам естественного языка сопоставлены группы цифр или букв. Употребление таких кодов приобрело значение скорее в связи со стремлением сэкономить на стоимости телеграмм, чем в связи с соображениями конспиративности (АВС-код В. Клаузен-Туэ, 1874).

Если каждый образ при кодировании является отдельным знаком, то такое отображение мы называем шифровкой, а образы - шифрами (англ. cipher).

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

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

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

Контрольные вопросы.

1. Что такое знак, алфавит, код, шифр 2. Чем код отличается от шифра 2. Кодирование информации Пусть объектом кодирования являются тексты, записанные на некотором (естественном или искусственном) языке, причем число букв в алфавите этого языка, включая (если есть такая необходимость) некоторые знаки препинания, знак пробела и т.п., равно п. Пусть далее, l - наименьшее натуральное число, удовлетворяющее условию. Тогда можно пользоваться простейшим из log l n различных методов побуквенного кодирования, сводящимся к установлению взаимно однозначного соответствия между различными буквами исходного текста и различными кодовыми наборами двоичных символов фиксированной длины, равной l. Например, если речь идет о текстах, записанных на русском языке, где число букв алфавита, включая знак пробела, n = 34, то, поскольку имеет место неравенство 5 < log234 < 6, можно осуществить побуквенное кодирование, установив следующее соответствие:

Буква русского Шестисимвольный Десятичная языка кодовый набор запись (пробел) 000000 а 000001 б 000010. ……….

л 001101. ………..

я 100001. ………..

. 111111 Декодирование при этом осуществляется очень просто: последовательность двоичных символов - закодированный текст - делится на блоки из шести символов и каждый блок заменяется соответствующей буквой алфавита исходного текста. Невооруженным глазом видно, что, будучи очень привлекательным по своей простоте, рассмотренный метод кодирования грешит определенной "расточительностью" (избыточностью). Об этом свидетельствует хотя бы то обстоятельство, что шестью двоичными символами мы смогли бы выразить не п = 34, а целых п = 26 = 64 букв алфавита. Чтобы улучшить положение, можно было, например, пойти на некоторую уступку, а именно, согласиться с тем, чтобы при кодировании и декодировании текстов пары букв "е"-"ё" и "ь"-"ъ" оказались "неразличимыми". Ведь люди, владеющие русским языком, все равно смогли бы восстановить это различие при работе с уже декодированным текстом. При наличии такого согласия число букв в алфавите русского языка (включая знак пробела) оказалось бы равным п = 32, и поэтому можно было бы обойтись кодовыми наборами постоянной длины, равной l = log232 = 5. Тем самым, из каждых шести двоичных символов один символ можно было сэкономить. Из этого примера легко сделать вывод, что при побуквенном кодировании букв исходного текста кодовыми наборами постоянной длины наиболее компактное (экономное) кодирование удается осуществить тогда, когда число букв в алфавите можно представить как целую степень двойки:

n = 2l ( l = 1,2,...,). (2.1) Нарушение этого условия при указанном методе кодирования непременно приводит к некоторой избыточности. Возникает вопрос, а имеются ли резервы для дальнейшего сокращения среднего числа двоичных символов, отводимых под одну букву Оказывается, что такие резервы имеются, и даже тогда, когда п удовлетворяет условию (2.1), возможны варианты, когда кодирование можно осуществить таким образом, чтобы среднее число двоичных символов, отводимых под одну букву, оказалось меньше l = log2п.





Пусть алфавит исходного текста состоит из восьми букв А, В, С, D, Е, F, G, Н.

Поскольку п = 8 = 23, т.е. l = 1оg2n = 3, то при рассмотренном только что методе кодирования каждой букве ставился бы в соответствие кодовый набор постоянной длины, равной трем.

Пусть нам известны значения вероятностей того, что наугад взятая буква из текстов этого языка окажется буквой А, В, С, D, Е, F, G или Н:

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

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

Пусть п - число букв в алфавите, nk— число букв, кодовые наборы которых состоят из k двоичных символов, li - число двоичных символов в кодовом наборе i-й буквы алфавита, L = max (li).

L Тогда, очевидно, =, а для произвольного фиксированного значения k nn k k=k имеет место. Если же нам заданы значения,...,,, то, очевидно, n 2 n n n -k 21 k будет иметь место неравенство k k -- -... - 22 nn 2 n k k -1 k - jk k т.е.

n j j=или, после деления обеих частей неравенства на 2k, k - j n j j=Поскольку выбор значения k произвольный, то примем k = L. и тогда будем иметь:

L - j n j j=Отсюда непосредственно следует n l i (2.2) i=Неравенство (2.2) называется неравенством Крафта и имеет ключевое значение в теории кодирования. Хотя вывод этого неравенства мы осуществили применительно к двоичному префиксному коду оно верно также для, произвольного (не обязательно двоичного и не обязательно префиксного) кода без запятой.

Неравенство Крафта, собственно, и лимитирует наше желание оперировать как можно меньшими значениями li. Пусть, например, n = 10 и уже известны значения l1 = 2, l2 = l3 =...= l6 = 3. Тогда. очевидно, значения l7 l10 должны удовлетворить неравенству - -- l i - - = 12 2 5 i=Пусть, например, мы хотим, чтобы имело место l7=l8=l9=l10=l.

Тогда получим, что значение l должно удовлетворить неравенству -l, т.е. оно не может быть меньше пяти.

4 2 1/ Префиксный код называется полным, если добавление к нему любого нового кодового набора нарушает свойство префиксности. Пусть, например, буквам А, В и С поставлены в соответствии кодовые наборы 00, 01 и 1. Тогда очевидно, что любая попытка закодировать еще хоть одну букву привела бы к нарушению свойства префиксности. Значит, код 00, 01, 1 является полным. Если же буквам А.

В и С были поставлены в соответствие кодовые наборы 00, 01 и 10, то через ветвь 11... мы смогли бы, не нарушая свойство префиксности, закодировать сколько угодно новых букв. Мы также смогли бы без нарушения свойства префиксности через ветвь 01... закодировать сколько угодно новых букв, если бы буквам А, В и С были поставлены в соответствие кодовые наборы 000, 001 и 1. Значит, коды 00, 01, 10 и 000, 001, 1 являются неполными. Для полных префиксных кодов и только для них неравенство Крафта превращается в равенство. Естественно, что на практике наибольший интерес представляют полные коды, так как при прочих равных условиях средняя длина кодовых наборов у полных кодов получается меньше, чем у неполных.

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

2.1. Схема двоичного кодирования текстов по Р. Фано Предложенная американским специалистом Р. Фано схема двоичного кодирования сводится к выполнению следующих операций.

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

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

3) Приписать произвольному одному из этих подмножеств (подсписков) символ "0", а другому - "1".

4) Рассматривая каждое из этих подмножеств (подсписков) как исходное, применительно к каждому из них осуществить операции, указанные в пунктах (2) и (3).

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

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

Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.