Кодирование инф. Курс лекций по темам раздела Кодирование информации, методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки
 Скачать 1.18 Mb.
|
|
условия: • Вес наименьшей значащей цифры (q 1 ) равен 1; • Вес второй значащей цифры (q 2 ) равен 1 или 2; 68 • Вес, соответствующий двум оставшимся цифрам кода, должен быть не меньше семи (q 3 +q 4 ≥7), если q 2 =1, и не меньше шести (q 3 +q 4 ≥6), если q 2 =2; • Совокупность весов должна удовлетворять соотношению q 4 –(q 1 +q 2 +q 3 )≤1. Двоично-десятичные коды широко применяются в АЦП, предназначенных для различных цифровых измерительных приборов. Каждая значимая десятичная цифра в таком коде представляется четырьмя двоичными знаками и содержит десять значений сигнала от 0 до 9. Для кода 8-4-2-1 представляется возможным производить арифметические операции на двоично-десятичных сумматорах, которые проектируют как обычные двоичные сумматоры, добавляя лишь устройства формирования дополнительных переносов, необходимых в тех случаях, когда сумма двух двоично-десятичных чисел S становится больше или равна 10. Причем, если 10≤S≤15, то после переноса в следующую четверть из суммы необходимо вычитать число 10 (1010), а если S = 16, то к сумме после переноса необходимо добавить 6 (0110). Например, при сложении двух двоично-десятичных чисел 0111 и 0100 получится число 1011, которое в двоично-десятичном изображении не предусмотрено. После переноса и коррекции суммы получим число 0001 0001. Для упрощения двоично-десятичных счетчиков процедуру вычитания числа 1010 заменяют двумя процедурами: вычитания числа 16 и добавления 6, что сводится к добавлению к сумме двоично-десятичного числа 01010 и переносу единицы в следующую четверть без восстановления. Так, для рассмотренного примера получим 1011+ 0110 = 1 0001. Описанный способ построения двоично-десятичных 69 счетчиков не исключает и возможности преобразования двоично-десятичного кода в натуральный двоичный код с последующим проведением арифметических операций. Вопросы для самопроверки: 1. Сформулируйте условия, необходимые для построения двоично-десятичного кода. 2. Получите двоично-десятичный код с весами 8-4-2-1 для числа 65 10 . 3. Расскажите о практическом применении двоично- десятичных кодов. Цифровые коды. Код Грея. При ответе на данный вопрос необходимо рассказать о характерных особенностях, алгоритме кодирования и правилах декодирования кода Грея, а также о способах его применения на практике. Особое место среди позиционных двоичных кодов занимает циклический код, называемый кодом Грея. Характерной особенностью этого кода является изменение только одной позиции при переходе от одного кодовой комбинации к другой. Это свойство кода Грея широко используют как для построения некоторых типов АЦП, так и для повышения надежности преобразователей с помощью резервирования и самоконтроля. Используется в технике аналогово-цифровых преобразователях, где он позволяет свести к «1» младшего разряда погрешность неоднозначности при считывании. Рассмотрим алгоритм построения кода Грея. Код Грея можно построить на основе натурального двоичного кода числа. 70 Для перехода от натурального двоичного кода к коду Грея существуют правила: • если в предыдущем разряде двоичного кода стоит 0, то в данном разряде цифра сохраняется; • если в предыдущем разряде двоичного кода стоит 1, то в данном разряде цифра меняется на противоположную (цифра 0 изменится на 1 и наоборот). Рассмотрим пример. Возьмем целые десятичные числа от 0 до 15. Запишем их двоичное представление, выделив для хранения каждого числа полбайта: А 10 0 1 2 3 4 5 6 7 А 2 0000 0001 0010 0011 0100 0101 0110 0111 А 10 8 9 10 11 12 13 14 15 А 2 1000 1001 1010 1011 1100 1101 1110 1111 Перейдем к построению кода Грея. Натуральный двоичный код числа 0 (0000) не содержит ни одной единицы. Следовательно, согласно правилу построения ни одна его цифра в коде Грея не изменится. Код числа 1 (0001) содержит одну единицу только в самом последнем справа разряде. Разряда для которого она являлась бы предыдущей нет. Значит натуральный двоичный код числа 1 совпадает с кодом Грея числа 1. А вот двоичный код числа 2 (0010) содержит единицу во третьем слева разряде. Согласно правилу построения кода Грея, следующий за ней разряд должен изменить свою цифру на противоположную. Значит код Грея для числа 2 будет 0011. Аналогичным образом можно получить код Грея для оставшихся чисел. Результат такого преобразования представлен в таблице. Разряды двоичного кода, подвергнутые изменению подчеркнуты: 71 А 10 0 1 2 3 4 5 6 7 А 2 0000 0001 0010 0011 0100 0101 0110 0111 Код Грея 0000 0001 0011 0010 0110 0111 0101 0100 А 10 8 9 10 11 12 13 14 15 А 2 1000 1001 1010 1011 1100 1101 1110 1111 Код Грея 1100 1101 1111 1110 1010 1011 1001 1000 Код Грея можно построить и с помощью графа. Покажем алгоритм построения на рассмотренном примере. Мы имеем числа от 0 до 15. Расположим их на концевых узлах будущего дерева. Объединим парами данные числа. При этом слева от каждого узла, поставим единицу, а справа нуль. Для получения по этой схеме кода Грея нужно в каждой второй справа в своем ряду «вилке» (на рисунке эти узлы отмечены знаком ) поменять местами 1 и 0. Теперь при прохождении по измененному графу от корня до концевых узлов мы сможем определять код Грея для выбранного числа. 72 Основными трудностями, ограничивающими применение кодов Грея, является непостоянство веса каждого разряда и изменение его знака. Выясним, как определяется вес и знак разряда кода Грея. Выберем кодовые комбинации, содержащие только одну единицу: 0001, 0010, 0100, 1000. Этим комбинациям соответствуют числа в десятичной системе счисления: 1, 3, 7, 15, которые определяют вес каждого разряда. С другой стороны, вес разряда может быть как положительным, так и отрицательным. Например, число 2 имеет код Грея 0011. Покажем ее представление с учетом веса каждого разряда: 15*0 + 7*0 + 3*1 + (-1)*1 = 3-1 = 2 Получили, что вес второго разряда положительный, а первого отрицательный (нумерация разрядов идет справа налево). Рассмотрим еще один пример. Получим представление числа 10. Его код Грея 1111. С учетом весовых коэффициентов имеем: 15*1 + (-7)*1 + 3*1 + (-1)*1 = 15 - 7 + 3 - 1 = 10 Здесь два разряда имеют положительный вес, а два отрицательный. Исследование особенностей построения кода Грея позволяет сделать вывод: его недостатком является то, что в нем затруднено, хотя и возможно, выполнение арифметических операций и цифроаналоговое преобразование. Поэтому в тех случаях, когда эти операции необходимы, параллельный код Грея превращают в натуральный двоичный, а 73 уже затем осуществляют арифметические операции или цифроаналоговое преобразование. Для перехода от кода Грея к натуральному двоичному коду используют следующее правило: если слева от данной цифры находится четное число единиц, то цифра сохраняется, в противном случае цифра меняется. Например имеет код Грея некоторого числа: 1010. Необходимо получить само число. Рассмотрим разряды кода слева направо. Обозначим их q 1 , q 2 , q 3 , q 4 . Левее q 1 других цифр нет, значит она не меняется. Второй разряд q 2 =0, слева от него находиться единственная единица, значит значение этого разряда меняется на на 1. Следующий разряд q 3 =1, в коде Грея ему также предшествует одна единица в разряде q 1 Следовательно цифра разряда q 3 поменяется на противоположную (q 3 = 0). А вот четвертому разряду кода Грея предшествуют уже две единицы в разрядах q 1 и q 3 , соответственно, значение этого разряда должно измениться. Окончательно имеем следующий двоичный код: 1100. Это двоичное представление числа 12. Вопросы для самопроверки: 1. Сформулируйте правила перехода от натурального двоичного кода к коду Грея. 2. Объясните алгоритм построения кода Грея с помощью графа. 3. Сформулируйте алгоритм перехода от кода Грея к натуральному двоичному коду. 74 Помехоустойчивое кодирование: основная идея, используемые понятия. При ответе на данный вопрос необходимо дать понятие помехоустойчивого кода, рассказать о классификации помехоустойчивых кодов и основных правилах их построения. Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных им в виде основной теоремы для дискретного канала с шумом: при любой скорости передачи двоичных символов меньшей, чем пропускная способность канала, существует такой код, при котором вероятность ошибочного декодирования будет сколь угодно мала; вероятность ошибки не может быть сделана произвольно малой, если скорость передачи больше пропускной способности канала. Кодирование должно осуществляться так, чтобы сигнал, соответствующий принятой последовательности символов, после воздействия на него предполагаемой в канале помехи оставался ближе к сигналу, соответствующему конкретной переданной последовательности символов, чем к сигналам, соответствующим другим возможным последовательностям (степень близости обычно определяется по числу разрядов, в которых последовательности отличаются друг от друга). Это достигается ценой введения при кодировании избыточности, которая позволяет так выбрать передаваемые последовательности символов, чтобы они удовлетворяли дополнительным условиям, проверка которых на приемной стороне дает возможность обнаружить и исправить ошибки. Коды, обладающие таким свойством, получили название помехоустойчивых. Они используются как для исправления ошибок (корректирующие коды), так и для их обнаружения. 75 У подавляющего большинства существующих в настоящее время помехоустойчивых кодов указанные выше условия являются следствием их алгебраической структуры. В связи с этим их называют алгебраическими кодами. Алгебраические коды можно подразделить на два больших класса: блоковые и непрерывные. В случае блоковых кодов процедура кодирования заключается в сопоставлении каждой букве сообщения (или последовательности из k символов, соответствующей этой букве) блока из n символов, причем в операциях по преобразованию принимают участие только указанные k символов и выходная последовательность не зависит от других символов в передаваемом сообщении. Блоковый код называется равномерным, если n остается постоянным для всех букв сообщения. Различают разделимые и неразделимые блоковые коды. При кодировании разделимыми кодами выходные последовательности состоят из символов, роль которых может быть отчетливо разграничена. Это информационные символы, совпадающие с символами последовательности, поступающей на вход кодера канала, и избыточные (проверочные) символы, вводимые в исходную последовательность кодером канала и служащие для обнаружения и исправления ошибок. При кодировании неразделимымикодами разделить символы выходной последовательности на информационные и проверочные невозможно. Непрерывными называются такие коды, в которых введение избыточных символов в кодируемую последовательность информационных символов осуществляется непрерывно, без разделения ее на независимые блоки. 76 Непрерывные коды также могут быть разделимыми и неразделимыми. При взаимно независимых ошибках наиболее вероятен переход в кодовую комбинацию, отличающуюся от данной в наименьшем числе символов. Степень различия любых двух кодовых комбинаций характеризуется расстоянием между ними (по Хэммингу), или просто кодовым расстоянием. Оно выражается числом символов, в которых комбинации отличаются одна от другой, и обозначается через d. Чтобы рассчитать кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2. Например заданы две кодовые комбинации А и В. Требуется определить кодовое расстояние. Складывая по модулю 2 каждый разряд А и В, получаем некоторую комбинацию С. Непосредственный подсчет единиц определяет вес (С) кодовой комбинации С, ϖ который равен кодовому расстоянию d. А: 1 0 0 1 1 1 1 1 0 1 (А)=7 ϖ + В: 1 1 0 0 0 0 1 0 1 0 (В)=4 ϖ С: 0 1 0 1 1 1 0 1 1 1 (С)=7. ϖ Следовательно, расстояние Хемминга для данных кодовых комбинаций d=7. Минимальное расстояние, взятое по всем парам кодовых комбинаций данного кода, называется минимальным кодовым расстоянием. Декодирование после приема может производиться таким образом, что принятая кодовая комбинация отождествляется с той разрешенной, которая отличается от полученной в наименьшем числе символов. 77 Такое декодирование называется декодированием по методу максимального правдоподобия. Вопросы для самопроверки: 1. Сформулируйте основную теорему для дискретного канала с шумом. 2. Расскажите о классификации помехоустойчивых кодов. 3. Вычислите расстояние Хемминга для следующей пары кодовых комбинаций: 10101001 и 11101101. Шифрование. Основные понятия. При ответе на данный вопрос необходимо раскрыть основные понятия теории шифрования (шифр, шифрование, ключ), дать классификацию шифров. Шифр - система преобразования текста для обеспечения секретности передаваемой информации. Сам термин происходит от арабского sifr - «ноль», преобразованного впоследствии во французское chiffre - «цифра». Шифры применяются для тайной переписки дипломатических представителей со своими правительствами, а также в вооруженных силах для передачи текста секретных документов по техническим средствам связи. Шифр может представлять собой совокупность условных знаков (условная азбука из цифр или букв) либо алгоритм кодирования с использованием обычных цифр и букв. Процесс засекречивания сообщения с помощью шифра называется шифрованием. Наука о создании и использовании шифров называется криптографией. Наука о методах получения исходного значения зашифрованной информации называется 78 криптоанализ. Слово «криптограф» происходит от древнегреческих слов kryptos 'секрет' и graphos 'писание'. Исходное сообщение называется в криптографии открытым текстом, или клером. Засекреченное (зашифрованное) сообщение называется шифротекстом, или шифрограммой, или криптограммой. Важным параметром любого шифра является ключ — параметр криптографического алгоритма, обеспечивающий выбор одного преобразования из совокупности преобразований, возможных для этого алгоритма. В современной криптографии предполагается, что вся секретность криптографического алгоритма сосредоточена в ключе, но не деталях самого алгоритма (принцип Керкгоффса). Шифры могут использовать один ключ для шифрования и дешифрования или два различных ключа. По этому признаку различают: • Симметричный шифр использует один ключ для шифрования и дешифрования. Ключ алгоритма должен сохраняться в секрете обеими сторонами. Алгоритм шифрования выбирается сторонами до начала обмена сообщениями. Классическим примером таких алгоритмов являются симметричные криптографические алгоритмы: простая перестановка, одиночная перестановка по ключу, двойная перестановка, перестановка «Магический квадрат». • Асимметричный шифр использует два различных ключа. Асимметричная система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифровки сообщения используется секретный ключ. 79 Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Шифры могут быть сконструированы так, чтобы либо шифровать сразу весь текст, либо шифровать его по мере поступления. Таким образом существуют: • Блочный шифр, который обрабатывает открытый текст блоками по несколько (как правило 8 или 16) байт за одну итерацию. Если исходный текст (или его остаток) меньше размера блока, перед шифрованием его дополняют. Преобразование текста должно использовать принципы рассеивания (изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста) и перемешивания (использование преобразований, затрудняющих получение статистических зависимостей между шифротектстом и открытым текстом). К достоинствам блочных шифров относят похожесть процедур шифрования и расшифрования, которые, как правило, отличаются лишь порядком действий. Это упрощает создание устройств шифрования, так как позволяет использовать одни и те же блоки в цепях шифрования и дешифрования. • Поточный шифр шифрует информацию и выдает шифротекст по мере поступления, таким образом имея возможность обрабатывать текст неограниченного размера используя фиксированный объем памяти. При использовании поточного шифра каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. 80 Естественно, что блочный шифр можно превратить в поточный, разбивая входные данные на отдельные блоки и шифруя их по отдельности. Важнейшим достоинством поточных шифров перед блочными является высокая скорость шифрования, соизмеримая со скоростью поступления входной информации; поэтому, обеспечивается шифрование практически в реальном масштабе времени вне зависимости от объема и разрядности потока преобразуемых данных. В синхронных поточных шифрах (в отличие от блочных) отсутствует эффект размножения ошибок, то есть число искаженных элементов в расшифрованной последовательности равно числу искаженных элементов зашифрованной последовательности, пришедшей из канала связи. Структура поточного ключа может иметь уязвимые места, которые дают возможность криптоаналитику получить дополнительную информацию о ключе (например, при малом периоде ключа криптоаналитик может использовать найденные части поточного ключа для дешифрования последующего закрытого текста). Поточные шифры в отличие от блочных достаточно часто взламываются при помощи линейной алгебры. Также для взлома поточных шифров весьма успешно применяется линейный и дифференциальный анализ. Вопросы для самопроверки: 1. Приведите примеры шифра и шифрования. 2. Определите предмет и объект исследования криптографии и криптоанализа. 3. Расскажите о классификации шифров. 81 |