Кодирование инф. Курс лекций по темам раздела Кодирование информации, методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки
 Скачать 1.18 Mb.
|
|
Возможность обнаружения и исправления ошибок В зависимости от возможности обнаружения и исправления ошибок в полученных по каналу связи кодах различают простые и корректирующие коды. В простых кодах все возможные кодовые комбинации используются непосредственно для передачи информациии ошибка в приеме хотя бы одного элемента кодовой комбинации приводит к неправильной регистрации передаваемого сообщения. В простых равномерных кодах превращение одного символа комбинации в другой, например 1 в 0 или 0 в 1, приводит к появлению новой комбинации, т.е. к ошибке. Корректирующие коды - это коды, позволяющие по имеющейся в кодовой комбинации избыточности обнаруживать и исправлять определённые ошибки, появление которых приводит к образованию ошибочных или запрещенных комбинаций. Применяются при передаче и обработке информации в вычислительной технике, телеграфии, телемеханике и технике связи, где возможны искажения сигнала в результате действия различного рода помех. Кодовые слова корректирующих кодов содержат информационные и проверочные разряды (символы). В процессе кодирования при передаче информации из информационных разрядов в 29 соответствии с определёнными для каждого корректирующего кода правилами формируются дополнительные символы — проверочные разряды. При декодировании из принятых кодовых слов по тем же правилам вновь формируют проверочные разряды и сравнивают их с принятыми; если они не совпадают, значит при передаче произошла ошибка. Существуют коды, обнаруживающие факт искажения сообщения, и коды, исправляющие ошибки, т.е. такие, с помощью которых можно восстановить первичную информацию. Критерий классификации: Число одновременно кодируемых символов первичного алфавита Исходя из числа одновременно кодируемых символов первичного алфавита кодирование классифицируют на алфавитное и блочное. При алфавитном кодировании передаваемое сообщение представляет собой последовательность кодов отдельных знаков первичного алфавита. Однако возможны варианты кодирования, при которых кодовый знак относится сразу к нескольким буквам первичного алфавита (будем называть такую комбинацию блоком) или даже к целому слову первичного языка. Кодирование блоков понижает избыточность. Применение блочного метода кодирования имеет свои недостатки. Во- первых, необходимо хранить огромную кодовую таблицу и постоянно к ней обращаться при кодировании и декодировании, что замедлит работу и потребует значительных ресурсов памяти. Во-вторых, помимо основных слов разговорный язык содержит много производных от них, например, падежи существительных в русском языке или глагольные формы в английском; в данном способе кодирования им всем нужно присвоить свои коды, что 30 приведет к увеличению кодовой таблицы еще в несколько раз. В- третьих, возникает проблема согласования (стандартизации) этих громадных таблиц, что непросто. Наконец, в-четвертых, алфавитное кодирование имеет то преимущество, что буквами можно закодировать любое слово, а при кодировании слов – можно использовать только имеющийся словарный запас. Вопросы для самопроверки: 1. Расшифруйте сообщение S = 04061501, если известно, что это равномерный код, в котором каждой букве кирилицы ставится в соответствие ее порядковый номер в алфавите минимально возможной длины. 2. Приведите пример многопозиционного кода. 3. Приведите пример блочного кодирования. Неравномерный код с разделителем. При ответе на этот вопрос необходимо определить основные свойства и правила построения неравномерного кода с разделителем, привести пример построения такого кода при заданном наборе правил построения. Неравномерный код с разделителями должен обладать следующими свойствами: • длина кода для различных символов первичного алфавита различна; • существуют разделители символов, слов или предложений (сообщений). Рассмотрим пример построения такого кода. Определим правила построения: 31 • будем применять алфавитное кодирование - каждая буква первичного алфавита будет иметь собственный уникальный код; • введем разделители символов — разделителем отдельных кодов будет последовательность двух нулей «00»; • введем разделители слов — это будет последовательность трех нулей «000» - пробел; • код признака конца символа включим в код символа, так как код признака конца символа не используется сам по себе, отдельно от кода символа, следовательно все коды символов будут заканчиваться на «00»; • коды символов не должны содержать двух (или более) нулей подряд нигде кроме как в конце кода. В противном случае такой код будет воспринят как два кода двух различных знаков первичного алфавита; • код символа не должен начинаться с «0», в противном случае ноль в начале кода текущего символа и два нуля в конце кода предыдущего символа будут образовывать код пробела. • т. к. разделителю слов «000» всегда предшествует признак конца знака (конце каждого слова реализуется последовательность «00000»), то для однозначного декодирования нужно потребовать, чтобы коды символов оканчивались не более чем четырьмя нулями. В соответствии с перечисленными правилами можно построить таблицу кодов для кириллицы. Код пробела уже определен - «000» (можно рассмотреть этот код как совокупность порядкового номера символа - «0» и 32 признака конца символа - «00»). Коды остальных символов будем определять в порядке их распределения в таблице частоты использования букв русского языка (см. Приложение 2). При этом коды символов будем получать последовательным прибавлением единицы к коду предыдущего символа. При этом необходимо проверять получающиеся комбинации на соответствие выбранным правилам и отвергать кодовые последовательности не отвечающие этим правилам. Как видно из таблицы, чаще всего в словах русского языка встречается буква «о». Определим ей код «100»: к порядковому номеру предыдущего символа - «пробела» (порядковый номер 0) добавим единицу, в конце кода допишем два нуля как признак конца символа. Полученный код не противоречит принятым правилам. Поступая аналогично, определим коды букв «е, ё» - «1000» (1 2 +1 2 =10 2 — порядковый номер буквы в таблице, выраженный в двоичной системе счисления; два нуля в конце кода — признак конца символа), код буквы «а» - «1100», код буквы «и» - «10000», код буквы «т» - «10100», код буквы «н» - «11000», код буквы «с» - «11100». Все эти коды удовлетворяют установленным нами правилам построения кода. Применяя алгоритм построения кода к следующей букве таблицы (букве «р»), получим: номер буквы — 111 2 +1 2 = 1000 2 , к нему нужно добавить «00» - признак конца символа, но тогда код буквы «р» будет «100000», что противоречит последнему условию формирования нашего кода (коды символов должны оканчиваться не более чем четырьмя нулями). Увеличим порядковый номер символа еще на единицу: 1000 2 +1 2 = 1001 2 — и, приписав к нему справа два нуля, сформируем возможный код символа «р». Получим «100100». Однако и этот код тоже не 33 может быть кодом символа в нашем неравномерном коде с разделителем — он противоречит следующему правилу: «коды символов не должны содержать двух (или более) нулей подряд нигде кроме как в конце кода». Продолжаем увеличение порядкового номера кода символа. Следующий возможный код - «101000». Он удовлетворяет всем правилам построения нашего кода и может быть выбран в качестве кода буквы «р». Действуя аналогично можно определить коды для всех символов алфавита: Буква пробел o е, ë а и Код 000 100 1000 1100 10000 Буква т н с р в Код 10100 11000 11100 101000 101100 Буква л к м д п Код 110000 110100 111000 111100 1010000 Буква у я ы з ъ, ь Код 1011000 1011100 1101000 1101100 1110000 Буква б г ч й х Код 1110100 1111000 1111100 10101000 10101100 Буква ж ю ш ц щ Код 10110000 10110100 10111000 10111100 11010000 Буква э ф Код 11010100 11011100 В итоге имеем неравномерный код, в котором длина кода для разных символов изменяется от 3 до 8 символов. Найдем среднюю длину кода для данного способа кодирования: 34 K ℘ ,Cyrilic, 2 = ∑ i= 0 32 P i n i ≈ 5,5 Здесь P i - частота использования i-й буквы, n i - это длина кодового слова для i-й буквы. Определим избыточность кодирования, учитывая, что средний информационный вес символа русского алфавита равен 4,72 бита: Q ℘ ,Cyrilic, 2 = K ℘ ,Cyrilic, 2 I A − 1= 5,5 4,72 − 1≈0,17 Это значит, что при данном способе кодирования мы будем вынуждены передавать на 17% больше информации, чем содержится в исходном сообщении. Вопросы для самопроверки: 1. Сформулируйте основный правила построения неравномерного кода с разделителем. 2. Может ли для выбранного в параграфе набора правил построения неравномерного кода существовать символ с кодом 11001000? 3. Постройте неравномерный двоичный код с разделителем для первичного алфавита {«+», «-», «*», «/»}. Префиксные коды. Условие Фано. Примеры. При ответе на этот вопрос необходимо объяснить понятие «префикс», дать определение префиксного кода, сформулировать условие Фано, привести примеры префиксных кодов. В языковедении термин «префикс» означает «приставка». 35 Префиксный код в теории кодирования — код со словом переменной длины, удовлетворяющий условию Роберта Фано. Условие Фано: неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо другого, более длинного кода. Например, если один из символов первичного алфавита имеет код «110» то в качестве кодов других символов нельзя использовать последовательности «1», «11», но можно использовать «0», «10». Декодирование для префиксных кодов однозначно и выполняется слева направо. При этом сопоставление с таблицей кодов всегда дает точное указание конец одного кода и начало другого. Это дает возможность не использовать разделители. Заметим, что любой код со словом фиксированной длины также является префиксным. Примерами префиксных кодов служат: совокупность телефонных номеров в стационарных сетях, Юникод, код Хаффмана. Рассмотрим пример собственного префиксного кода:. Пусть требуется составить префиксный код для первичного алфавита А={а, л, м, р, у, ы}. В качестве вторичного алфавита возьмем двоичный алфавит B={0; 1}. Определим для символа «а» код «00». Для выполнения условия Фано коды других символов не должны начинаться с «00». Букве «л» определим код «01», «м» - код «100», «р» - код «101». Коды оставшихся букв должны начинаться с «11»: пусть код буквы «у» будет «110», а код буквы «ы» - «111». a i а л м р у ы Код 00 01 100 101 110 111 36 Теперь, используя построенную таблицу кодов, декодируем сообщение: 1000010000100111010010100100110 Начинать следует слева направо, последовательно вычеркивая обнаруженные коды, и записывая соответствующие им знаки первичного алфавита. Символа с кодом «1» не существует. Добавляем к «1» следующую цифру кода - «0». Символа с кодом «10» в кодовой таблице тоже нет. Присоединяем следующую цифру кодовой последовательности. Получаем код «100». Это код буквы «м». Собираем код следующей буквы. Символа с кодом «0» в таблице нет. Присоединение к коду следующей цифры кодовой последовательности дает нам код «00» - код буквы «а». Поступая аналогично можно получить однозначный вариант расшифровки (декодирования) заданного сообщения: 100 00 100 00 100 111 01 00 101 00 100 110 м а м а м ы л а р а м у Вопросы для самопроверки: 1. Сформулируйте условие Фано. 2. Приведите примеры существующих префиксных кодов? 3. Определите является ли префиксным следующий двоичный код первых 5 букв латинского алфавита: a b c d e 000 110 01 001 10 Декодируйте сообщение 1100000100110, записанное с использованием приведенного кода. 37 Префиксный код Шеннона-Фано. При ответе на данный вопрос необходимо привести пример построения префиксного кода Шеннона-Фано для заданного начального алфавита и известных частот использования символов этого алфавита с помощью таблицы и графа. В 1948-1949 гг. Клод Шеннон (Claude Elwood Shannon) и Роберт Фано (Robert Mario Fano) независимо друг от друга предложили префиксный код, названный в последствие в их честь. Алгоритм Шеннона — Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его первичного алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями. Рассмотрим алгоритм построения этого кода на примере. Пусть имеется первичный алфавит, состоящий из шести символов: {A; B; C; D; E; F}, также известны вероятности появления этих символов в сообщении, они равны соответственно 0,15; 0,2; 0,1; 0,3; 0,2; 0,05. Расположим эти символы в таблице в порядке убывания их вероятностей. Первичный алфавит D B E A C F Вероятность появления 0,3 0,2 0,2 0,15 0,1 0,05 Кодирование осуществляется следующим образом. Все символы делятся на две группы с сохранением порядка следования (по убыванию вероятностей появления), так чтобы суммы вероятностей в каждой группе были приблизительно 38 равны, а, следовательно, абсолютные разности суммарных вероятностей каждой группы близки к нулю. В нашем примере в первую группу попадают символы D и B (их суммарная вероятность использования равна 0,5), все остальные буквы (также имеющие суммарную вероятность появления 0,5) попадают во вторую группу. Поставим ноль в первый знак кодов для всех символов из первой группы, а первый знак кодов символов второй группы установим равным единице. Продолжим деление каждой группы. В первой группе два элемента, и деление на подгруппы здесь однозначно: в первой подгруппе будет символ D, а во второй - символ B. Во второй группе теоретически возможны три способа деления на подгруппы: {E} и {A, C, F}, {E, A} и {C, F}, {E, A, C} и {F}. Но в первом случае абсолютная разность суммарных вероятностей будет |0,2 — (0,15 + 0,1 + 0,05)| = 0,1. Во втором и третьем варианте деления аналогичные величины будут 0,2 и 0,4 соответственно. Согласно алгоритму необходимо выбрать тот способ деления, при котором суммы вероятностей в каждой подгруппе были примерно одинаковыми, а, следовательно, вычисленная разность минимальна. Соответственно наилучшим способом деления будет следующий вариант: символ {E} остается в первой подгруппе, а символы {A, C, F} образуют вторую группу. Далее по имеющемуся алгоритму распределим нули и единицы в соответствующие знаки кода каждой подгруппы. Осуществляем деление на подгруппы по той же схеме до тех пор, пока не получим группы, состоящие из одного элемента. Процедура деления изображена в нижеприведенной таблице (символ «Х» означает, что данный знак кода отсутствует): 39 П ер ви чн ы й а лф ав ит В ер оя тн ос ти по яв ле ни я с им во ло в Знаки кода символа К од с им во ла Д ли на к од а I II III IV D 0,3 0 0 Х Х 00 2 B 0,2 0 1 Х Х 01 2 E 0,2 1 0 Х Х 10 2 A 0,15 1 1 0 Х 110 3 C 0,1 1 1 1 0 1110 4 F 0,05 1 1 1 1 1111 4 Данный код может быть построен и с помощью графа. Распределим символы алфавита в порядке убывания вероятностей — это будут концевые вершины (листья) будущего двоичного дерева (нижние индексы соответствуют вероятностям появления символов): D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05 Согласно алгоритму построения кода Шеннона-Фано разобьем эти символы на две группы с приблизительно равными суммарными вероятностями появления. Порядок следования символов при этом изменять нельзя. Для нашего первичного алфавита в первую группу войдут символы D и B, а во вторую E, A, C и F. Соединим первые символы каждой группы с корнем дерева: 40 D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05 Продолжаем построение графа по приведенному алгоритму, соединяя первые символы получающихся подгрупп с узлами ветвления более высоких уровней. Таким образом, на следующем этапе построения получим: D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05 Далее: D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05 Окончательно имеем следующий граф: D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05 Теперь для каждого узла ветвления обозначим каждую 41 левую исходящую дугу цифрой 0, а каждую правую исходящую дугу цифрой 1: D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05 Для получения кода символа достаточно пройти по дугам полученного дерева от корня к соответствующей вершине и записать номера дуг, по которым осуществляется движение. Например, для символа A, двигаясь от корня дерева, проходим дуги с номерами 1, 1 и 0, следовательно код символа A — 110. Аналогично могут быть получены коды других символов. Полученный код удовлетворяет условию Фано, следовательно он является префиксным. Средняя длина этого кода равна: K Шеннона−Фано,А, 2 = ∑ i=1 6 n i p i = 0,3∗20,2∗2 0,2∗20,15∗30,1∗40,05∗4=2,45 символов Среднее количество информации на один символ первичного алфавита равно: I A = - (0,3* log 2 0,3 + 0,2* log 2 0,2 + 0,2* log 2 0,2 + 0,15* log 2 0,15 + + 0,1* log 2 0,1 + 0,05* log 2 0,05) = 2,41 бит. Теперь по известной нам формуле найдем избыточность кода Шеннона –Фано: Q(Шеннона-Фано, A, Binary) = 2,45/2,41 – 1 = 0,01659751. 42 |