Скляр Б. Цифровая связь (2003) (1151859), страница 211
Текст из файла (страница 211)
13.14. Входной алфавит (клавиатура текстового процессора) состоит из 100 символов. а) Если нажатие клавиши кодируется с помощью кода фиксированной длины, определите требуемое число бит для кодирования. б) Сделаем упрощающее предположхние, состоящее в том, оо 1О нажатий клавиш равновероятны и каждое происходит с вероятностью 0,05. Предположим также, что оставшиеся 90 нажатий клавиш равновероятны.
Определите среднее числа бит, требуемое для кодирования этого алфавита с использованием када Хаффмана перемешюй длины. 13.15. Используйте модифицированный МККТТ факсимильный код Хаффмана для кодирования следующей последовательности единственной строки из 2 047 черных и белых пикселей. Определите отношение закодированных битов к входным. 11Б (Ч 2Б 2Ч 4Б 4Ч 8Б ЗЧ 16Б 16Ч 32Б 32Ч 664Б 64Ч !28Б 128Ч 256Б 256Ч 5!2Б 5!2Ч 1Б 13.16.
)РЕО квантует спектральные составляющие, полученные с помощью ДКП четного расширения обработанных данных. Чтобы показать опгасительные потери ДКП и БПФ, образуйте четггое и скопированное расширения ряда (10 12 14 16 Гб 20 22 24), чтобы получить (10 12 14 16 18 20 22 24 1О 12 14 16 18 20 22 24) и (1О 12 14 16 18 20 22 24 24 22 20 18 16 14 !2 10). Примените ДПФ к двум временным рядам и сравните относитеяьный размер спектральных компонентов (отличных от постоянных составляющих).
Теперь дополните спектр, полагая равными нулю все лепестки, кроме 5 спектральных. В четном расширении удерживаются лепестки 11 2 3 15 16), в то время как в периодическом — (1 3 5 13 15). Вычислите обратное ДПФ кюкдого и сравните атносителыгый размер ошибки восстановления для двух преобразований. 904 Глава 13. Кодирование источника 13.17. )РЕП использует зигзагообразную модель сканирования лля обращения к спектральным составляющим ДКП, доставленным квантуюшим устройством. Альтернативной моделью сканирования будет растровое сканирование, сканирование последовательных строк, обычно выполняемое при сканировании изображения. Сравните эффективность сканирования зигзагообразным методом с эффективностью растрового сканирования, если ненулевыми спектральными членами являются 5(0, 0) = 11001100, 5(1, 0) = !О!О! и 5(0, 1) = !!0001.
Используйте модифицированный код Хаффмана из табл. !3.1 для определения размеров групп нулей. Предположите, что следующая таблица определяет битовое присвоение на спектральный лепесток. 13.18. ДКП преобразует блок 8х8 пикселей, содержащий 8-битовые слова, в блок 8х8 спектральных выборок, содержащих число бит, определенных в таблице квантования задачи !3.17. Предполагается, что не существует последовательностей нулей переменной длины, так что в выходе ДКП представлен каждый лепесток; вычислите коэффициент сжатия (отношение входных битов к выходным), приписанный ДКП.
Вычислите коэффициент сжатия, предполагая, что количество значимых коэффициентов ДКП ограничено верхним треугольником таблицы квантования, состоящей из одного 8-битового слова, двух 6-битовых и трех 5- битовых, с оставшимися битами, которые описываются кодом лля 10! нуля. Вопросы для самопроверки 13.1. Почему сигналы подвергаются операциям кодирования лсюочлика, перед передачей или за- поминанием (см. разделы 13.1 и 13.7)? 13.2. Какие свойства яелреривяого сигнала позволяют представить его с помощью уменьшенного числа бит на выборку (см.
разделы 13.1, 1З.З и 13.7)? 13.3. Какие свойства дискретного сигнала позволяют представить его с помощью уменьшенного числа бит на символ (см. раздел 13, ! и 13.7)? 13.4. Большинство квантуюших устройств являются равномерными относительно размера шага. Существуют приложения, ддя которых требуются неравномерные квантуюшие устройства.
Они иногда называются комлалдярующимя квантуюшими устройствами. Зачем нужны подобные квантуюшие устройства (см. раздел ! 3.2.5)? 13.5. Аналого-цифровой преобразователь (апа!ой-го-д!8!(а! соптепег — А()С, АПП) представляет выборочные данные сигнала с помощью такого числа бит на выборку, которое удовлетнзряет требуемой точности. Болыиинстао А1(П являются квантуюшими устройствами без ламами, что означает, что каждое квазпование (преобразование) производится независимо от других преобразований. Как может использоваться память для ограничения числа бит на выборку (см. раздел 1З.З)? 13.6. Кодирование источника уменьшает язбыюочласть и отбрасывает несущественное солер;кимов. В чем состоит разница между избыточностью и несушесгвегпгостью (см.
раздел 3.7)? 13.7. Часто слышим такое высказывание, как "картина стоит тысячи слов". Действительно ли картина стоит тысячи слов (см. раздел 13.8.2Г Яоб 1чо о 14.1. Модели„цели и ранние системы шифрования 14.1.1. Модель процесса шифрования и дешифрование Желание общаться конфиденциально уходит своими корнями в далекое прошлое. История секретного общения богата уникальными изобретениями и красочными анекдотами 11].
Изучение путей передачи сообщений, которые не допускали бы постороннего вмешательства, называется криптографией. Термины шифрование и кодирование обозначают преобразования сообщений, выполняемые передатчиком, а термины дешифрование и декодирооание — обратные преобразования, производимые приемником. Основными причинами использования криптосистем в общении являются (1) обеспечение конфиденциальности, т.е. предотвращение извлечения информации из канала посторонним лицом (подслушивание); (2) аутентификация, предотвращение внедрения в канал информации посторонними людьми (обманный доступ). Часто, как в случае электронной пересылки или договорных переговоров, важно обеспечить электронный эквивалент письменной надписи. Это необходимо для того, чтобы устранить какие-либо недоразумения между отправителем и получателем относительного того, какое сообщение было отправлено и было ли оно вообще отправлено.
На рис. 14.1 изображена модель криптографического канала. Сообщение, или открытый текст М, шифруется с помощью обратимого преобразования Е», дающего шифрованный текст С= Е»(М). Шифрованный текст пропускается через незащищенный, или общедоступный канал. После получения шифрованного сообщения С, его исходное значение восстанавливается с помощью операции дешифрования, описываемой обратным преобразованием Р„= Е„', что выглядит следующим образом: 1),(С) =Е ~Е,(М))=М. (14.1) Открытый текат и Ключ Рис.
14.1. Модель криптографического канала Параметром К обозначается множество символов или характеристик, называемых ключолт, определяющим конкретное шифрующее преобразование Е» из семейства криптографических преобразований. Первоначально зашишенносп криптосистем зависела от секретности всего процесса шифрования, но в конечном итоге были разработаны системы, для которых общая природа преобразования шифрования или алгоритма могла быть общеизвестна, а секретность системы зависела от специального ключа. Ключ использовался для шифрования нешифрованного сообщения, а также для дешифрования шифрованного сообщения. Здесь можно отметить аналогию с универсальным компьютером и компью- 908 Глава 14 Шидтоовянио и псе ниатоттввнио тарной программой.
Компьютер, подобно криптосистеме, способен на множество преобразований, из которых компьютерная программа, подобно специальному ключу, выбирает одно. В большинстве криптосистем каждый, имеющий доступ к ключу, может как шифровать, так и дешифровать сообщения. Ключ передается авторизованным пользователям через секретный канал (в качестве примера может быль использован курьер для передачи из рук в руки важной ключевой информации); ключ, как правило, остается неизменным в течение значительного числа передач. Целью хриаяоаналияиха (противника) является оценка открытого текста М посредством анализа шифрованного текста, полученного из общедоступного канала, без использования ключа Схемы шифрования можно разбить на две основные категории: блочное и шифрование лоеока данных, или просто поточнее.
При блочном шифровании нешифрованный текст делится на блоки фиксированного размера, после чего каждый блок шифруется независимо. Следовательно, одинаковые блоки открытого текста с помощью данного ключа будут преобразовываться в одинаковые блоки шифрованного текста (подобно блочному кодированию), При поточном шифровании (подобном сверточному кодированию) блоков фиксированного размера не существует.
Каждый бит открытого текста т, шнфруется с помощью 1-го элемента х, последовательности символов (ключевого потока), генерируемой ключом. Процесс шифрования является лериодическин, если ключевой поток начинает повторяться после р символов (причем р фиксированно); в противном случае он является непериодическим. В общем случае схема шифрования существенно отличается от схемы канального кодирования.
Например, при шифровании данные открытого текста не должны явно фигурировать в шифрованном тексте, а при канальном кодировании в систематической форме коды часто содержат неизмененные биты сообщения плюс биты четности (см. раздел б.4.5). Существуют и другие отличия шифрования и канального кодирования. При блочном шифровании единственный бит ошибки на входе дешифратора может изменить значение многих выходных битов в блоке. Этот эффект, известный как накопление ошибки (епог ргорайайоп), часто является желаемым криптографическим свойством, поскольку для несанкционированных пользователей он создает дополнительные сложности при расшифровке сообщений. В то же время при канальном кодировании такое свойство является нежелательным, поскольку хотелось бы, чтобы система исправила как можно больше ошибок и на выходную информацию входные ошибки относительно не влияли. 14.1.2.
Задачи системы шифрсаанмя Основные требования к системе шифрования можно сформулировать следующим образом. 1. Обеспечить простые и недорогие средстве шифрования и дешифрования для авторизованных пользователей, обладающих соответствующим ключом. 2. Задачу криптоаналитика по производству оценки нешифрованного текста без помощи ключа сделать максимально сложиой и дорогой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
