Кодиpование пpоизвольно pаспpеделенных целых чисел

Содержание

Кодирование целых и действительных чисел

ЛЕКЦИЯ №2-3.

ПРЕДСТАВЛЕНИЕ ЧИСЕЛ, ТЕКСТОВОЙ И ГРАФИЧЕСКОЙ ИНФОРМАЦИИ В ЭВМ. СИСТЕМЫ СЧИСЛЕНИЯ.

ДАННЫЕ

Носители данных

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

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

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

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

Операции с данными

Можно выделить следующие основные операции:

сбор данных — накопление информации с целью обеспечения достаточной полноты для принятия решений;

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

фильтрация данных — отсеивание «лишних» данных, в которых нет необходимости для принятия решений;

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

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

защита данных — комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных;

транспортировка данных — прием и передача (доставка и поставка) данных между удаленными участниками информационного процесса; при этом источник данных в информатике принято называть сервером, а потребителя — клиентом;

преобразование данных — перевод данных из одной формы в другую или из одной структуры в другую.

Кодирование данных двоичным кодом

Естественные человеческие языки — это не что иное, как системы кодирования понятий для выражения мыслей посредством речи. Своя система существует и в вычислительной технике — она называется двоичным кодированием и основана на представлении данных последовательностью всего двух знаков: 0 и 1. Эти знаки называются двоичными цифрами, по-английски — binary digit или, сокращенно, bit (бит).

Одним битом могут быть выражены два понятия: 0 или 1. Если количество битов увеличить до двух, то уже можно выразить четыре различных понятия:

Увеличивая на единицу количество разрядов в системе двоичного кодирования, мы увеличиваем в два раза количество значений, которое может быть выражено в данной системе, то есть общая формула имеет вид:

N — количество независимых кодируемых значений;

m — разрядность двоичного кодирования, принятая в данной системе.

Кодирование целых и действительных чисел

Для перевода чисел из десятичной системы счисления в систему с основанием p>1 обычно используют следующий алгоритм:

1. Если переводится целая часть числа, то она делится на р, после чего запоминается остаток от деления. Полученное частное вновь делится на р, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на Р выписываются в порядке, обратном их получению.

Целые числа кодируются двоичным кодом достаточно.

19 2 18 9
8 4
4 2
2 1
0 0

Для кодирования целых чисел от 0 до 255 достаточно иметь 8 разрядов двоичного кода (8 бит). Шестнадцать бит позволяют закодировать целые числа от 0 до 65535, а 24 бита — уже более 16,5 миллионов разных значений.

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

Пример. Перевести данное число из десятичной системы счисления в двоичную (получить пять знаков после запятой в двоичном представлении).

Решение. а) 380 0 1875 380,1875(10)=101111100,0011(2)

Для кодирования действительных чисел используют 80-разрядное кодирование. При этом число предварительно преобразуется в нормализованную форму:

3,1415926 = 0,31415926·10 1

300 000 = 0,3·10 6

123 456 789 = 0,123456789 · 10 10

Первая часть числа называется мантиссой, а вторая — характеристикой. Большую часть из 80 бит отводят для хранения мантиссы (вместе со знаком) и некоторое фиксированное количество разрядов отводят для хранения характеристики (тоже со знаком).

Если необходимо перевести число из двоичной системы счисления в систему счисления, основанием которой является степень двойки, достаточно объединить цифры двоичного числа в группы по столько цифр, каков показатель степени, и использовать приведенный ниже алгоритм. Например, если перевод осуществляется в восьмеричную систему, то группы будут содержать три цифры (8=2 3 ). В целой части числа группировка производится справа налево, в дробной части — слева направо. Если в последней группе недостает цифр, дописываются нули: в целой части — слева, в дробной — справа. Затем каждая группа заменяется соответствующей цифрой новой системы. Соответствия приведены в таблице.

Переведем из двоичной системы в шестнадцатеричную число 1111010101,11(2). Решение 001111010101,1100(2)=3D5,C(16).

При переводе чисел из системы счисления с основанием р в десятичную систему счисления необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и дробной части, начиная с разряда сразу после запятой, слева направо (начальный номер — 1). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда.

Это и есть представление исходного числа в десятичной системе счисления.

Пример. Перевести данное число в десятичную систему счисления:

а) 1000001(2)=1·2 6 + 0·2 5 + 0·2 4 + 0·2 3 + 0·2 2 + 0·2 1 + 0·2 5 + 1·2 0 =65(10).

Замечание. Если в каком-либо разряде стоит нуль, то соответствующее слагаемое можно опустить.

б) 1000011111,0101(2)=1·2 9 + 1·2 4 + 1·2 3 + 1·2 2 + 1·2 1 + 1·2 0 + 1·2 -2 + 1·2 -4 = 512+16+8+4+2+1+0,25+0,0625=543,3125(10).

в) 1216,04(8)=1·8 3 + 2·8 2 + 1·8 1 + 6·8 0 + 4·8 -2 = 512+128+8+6+0,0625=654,0625(10).

г) 29А,5(16)=2·16 2 + 9·16 1 + 10·16 0 + 5·16 -1 = 512+144+10+0,3125=656,3125(10).

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

Кодирование целых и действительных чисел

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

Для кодирования целых чисел от 0 до 255 достаточно иметь 8 разрядов двоичного кода (8 бит). 16 бит позволяют закодировать целые числа от 0 до 65 535, а 24 бит — уже более 16,5 млн разных значений.

Для кодирования действительных чисел используют 80-раз- рядное кодирование. При этом число предварительно преобразуется в нормализованную форму:

Первая часть числа называется мантиссой, а вторая — характеристикой. Большую часть из 80 бит отводят для хранения мантиссы (вместе со знаком), и некоторое фиксированное количество разрядов отводят для хранения характеристики (тоже со знаком).

Кодирование данных

Читайте также:

  1. CHAR и VARCHAR2 — символьные типы данных Огасlе
  2. CRM – технологии и интеллектуальный анализ данных в управлении маркетингом.
  3. FPU предоставляет восемь регистров для хранения данных и пять вспомогательных регистров.
  4. RI +/- коррекция данных финансовой отчетности
  5. X. Логические основы ЭВМ. Кодирование данных в ЭВМ
  6. А. Функции для оценки разброса данных.
  7. Абстрактные структуры данных.
  8. Аварии на взрывоопасных и пожароопасных объектах, очаги поражения при данных авариях
  9. Автоматизация учета данных путевых листов малого АТП
  10. Автоматизированные банки данных
  11. АВТОМАТИЗИРОВАННЫЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ ДЛЯ КАМЕРАЛЬНОЙ ОБРАБОТКИ ТОПОГРАФО-ГЕОДЕЗИЧЕСКИХ ДАННЫХ
  12. Администратор базы данных и его функции

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

Компьютеры предпочитают работать с цифровыми данными из-за удобства их хранения и обработки. В вычислительной технике применяется двоичная система кодирования — она основана на представлении данных последовательностью всего двух знаков: 0 и 1, т. е. двоичной системы счисления. Эти знаки называют двоичными цифрами, т. е. битами. Одним битом могут быть выражены всего два понятия: 0 или 1 (да или нет, черное или белое, истина или ложь). Если количество битов увеличить до двух, то уже можно выразить четыре различных понятия: 00, 01, 10, 11. Тремя битами можно закодировать восемь различных значений: 000, 001, 010, 011, 100, 101, 110, 111. Увеличивая на единицу количество разрядов в системе двоичного кодирования, увеличивают в два раза количество значений, которое может быть выражено в данной системе.

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

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

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

Рис. 22 Кодирование информации

Кодирование числовой информации

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

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

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

В нормализованной форме число представляется в виде , где — мантисса числа, — основание системы счисления, — порядок числа.

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

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

Для кодирования целых чисел от 0 до 255 достаточно одного байта двоичного кода. Двумя байтами двоичного кода можно закодировать числа от 0 до 65535. Соответственно для трех байтов двоичного кода (24 бит) — 16,5 миллионов различных значений.

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

! Пример: Число имеет внутреннее представление в машинном слове , а в двойном машинном слове — .

Двоичные разряды в машинном слове нумеруются от 0 до 15 справа налево, Старший 15-й разряд в машинном представлении является знаковым. Поэтому для положительного числа он всегда равен нулю. Максимальное число в такой форме равно .

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

Описанный способ представления целого отрицательного числа называют дополнительным кодом. Старший разряд любого целого числа указывает на знак числа. Поэтому его называют знаковым.

Алгоритм получения дополнительного кода:

1. Дополнительный код положительного числа равен прямому коду этого числа.

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

! Пример: Число имеет внутренне представление в машинном слове (дополнительный код) .

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

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

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

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

На математической числовой оси вещественные числа образуют непрерывное множество, т. е. два числа могут сколь угодно близко находиться друг к другу, и на любом отрезке находиться бесконечное множество значений чисел. В машинном же представлении количество возможных значений чисел конечно; для двоичной системы счисления оно определяется как , где — количество двоичных разрядов в представлении мантиссы. Таким образом, в техническом устройстве непрерывный континуум вещественных чисел заменяется машинными кодами, образующими конечное дискретное множество — каждый код оказывается представителем целого интервала значений континуума (рис. 23).

Рис. 23 Дискретное представление вещественных чисел в ЭВМ

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

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

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

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

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

Кодирование символьной информации

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

В настоящее время принята и действует следующая договоренность, в соответствии с которой таблицу кодов разделили на три части (ASCII таблица):

– символы с кодами от 0 до 31используются в качестве управляющих кодов производителями компьютеров;

– символы с кодами от 32 до 127 являются стандартной кодировкой ASCII, включающей коды символов английского алфавита, знаки препинания, цифры, знаки арифметических действий и некоторые вспомогательные символы;

– символы с кодами от 128 до 255 отданы для создания в каждой стране своего стандарта.

В России в настоящее время действуют несколько таблиц кодировки.

F Таблица кодировки — это стандарт, ставящий в соответствие каждому символу алфавита свой порядковый номер.

В однобайтных таблицах кодировки наименьшим номером символа является 0, а наибольшим — 255.

F Двоичный код символа — это его порядковый номер в двоичной системе счисления.

Таким образом, таблица кодировки устанавливает связь между внешними символьным алфавитом компьютера и внутренним двоичным представлением. Международным стандартом для персональных компьютеров стала первая половина кодовой таблицы ASCII, т. е. разряды с 0 по 127. Существуют следующие кодировки второй половины таблицы ASCII для России:

1. Кодировка Windows 1251 — введена для кодирования российского алфавита компанией Microsoft.

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

3. ISO (International Standard Organization — международный институт стандартизации). На практике данная кодировка используется редко.

4. Кодировка ГОСТ-альтернативная — используется на компьютерах, работающих в операционных системах MS-DOS.

В настоящее время осуществляется постепенный переход на универсальную систему кодирования текстовых данных — UNICODE. Такая система, основанная на 16-разрядном кодировании (65536 различных кодовых комбинаций), позволяет разместить в одной таблице символы большинства языков планеты.

Кодирование графической информации

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

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

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

Для кодирования цветных графических изображений применяется принцип декомпозиции произвольного цвета на основные составляющие, т. е. информация в коде каждого пикселя должна содержать сведения о том, какую интенсивность (яркость) имеет каждая составляющая в его цвете. На практике считается, что любой цвет можно получить смешением трех основных цветов — красного (Red, R), зеленого (Green, G), синего (Blue, B). Система получила название — RGB. Чувствительность человеческого глаза более 16 миллионов различных цветов. Поэтому для кодирования цвета точки необходимо использовать три байта (24 разряда двоичного кода). При использовании дополнительных цветов — голубого (Cyan, C), пурпурного (Magenta, M) и желтого (Yellow, Y), которые дополняют до белого основные цвета — красный, зеленый и синий соответственно, можно значительно улучшить качество изображения. Такое кодирование называется полноцветным (True Color). При использовании для кодирования каждой цветовой точки двух байтового кода (16 бит) сокращается объем хранимых данных, но ухудшается цветовая гамма. Такой режим называют High Color.

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

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

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

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

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

Кодирование звуковой информации

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

Основной принцип кодирования звука, как и кодирования изображения, выражается словом «дискретизация». При кодировании изображения дискретизация — это разбиение рисунка на конечное число одноцветных элементов — пикселей. Чем меньше эти элементы, тем меньше наше зрение замечает дискретность рисунка. Физическая природа звука — это колебания в определенном диапазоне частот, передаваемые звуковой волной через воздух (или другую упругую среду).

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

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

В процессе записи звука аудиоадаптер с определенным периодом измеряет амплитуду электрического тока и заносит в регистр двоичный код полученной величины. Затем полученный код из регистра переписывается в оперативную память компьютера. Качество компьютерного звука определяется характеристиками аудиоадаптера: частотой дискретизации и разрядностью.

F Частота дискретизации — это количество измерений входного сигнала за 1 секунду.

Частота измеряется в герцах (Гц). Одно измерение за 1 секунду соответствует частоте 1 Гц. 1000 измерений за 1 секунду — 1 килогерц (кГц). Характерные частоты дискретизации аудиоадаптеров: 11 кГц, 22 кГц, 44,1 кГц и др.

F Разрядность регистра — число бит в регистре аудиоадаптера.

Рис. 25 Преобразование звуковых волн

Разрядность определяет точность измерения входного сигнала. Чем больше разрядность, тем меньше погрешность каждого отдельного преобразования величины электрического сигнала в число и обратно. Если разрядность равна 8 (16), то при измерении входного сигнала может быть получено ( ) различных значений. Очевидно, 16-ти разрядный аудиоадаптер точнее кодирует и воспроизводит звук, чем 8-ми разрядный.

F Звуковой файл — файл, хранящий звуковую информацию в числовой двоичной форме.

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

! Пример: Определить размер (в байтах) цифрового аудиофайла монофонического звучания, длительностью 10 секунд при частоте дискретизации 22,05 кГц и разрешении 8 бит. Файл сжатию не подвержен.
(байт).

4.3 Передача данных

| следующая лекция ==>
Общие сведения. Любой вариант процесса обработки данных происходит по схеме, представленной на рис |

Дата добавления: 2014-01-07 ; Просмотров: 3411 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Кодирование беззнаковых и знаковых целых чисел. Кодирование действительных чисел. Кодирование символов и строк.

• Беззнаковые целые числа:

• Переводятся в бинарные, записываются последовательно в младшие разряды, старшие заполняются нулями.

• Положительные знаковые целые числа:

• Самый старший бит не заполняется, в остальном как беззнаковые целые.

• Отрицательные знаковые целые числа:

• Бинарный код модуля инвертируется, добавляется бинарная единица, код записывается как беззнаковые целые.

• В старшие биты записывается мантисса, в младшие — порядок.

• Чем больше порядок, тем меньше точность.

• Многобайтовые: другие варианты.

• Беззнаковые целые представляют только неотрицательные числа, при этом все разряды кода используются для представления значения числа и максимальное число соответствует единичным значениям кода во всех разрядах: 111…111. m-байтовая переменная целого типа без знака, очевидно, принимает значения от 0 до +2 8 m −1.

• Однако для большинства современных процессоров обычным представлением чисел со знаком является дополнительный код. Максимальное положительное число представляется двоичным кодом 0111…111, максимальное по модулю отрицательное кодом 1000…000, а код 111…111 соответствует −1. Такое представление чисел соответствует наиболее простой реализации арифметических логических устройств процессора на логических вентилях и позволяет использовать один и тот же алгоритм сложения и вычитания как для беззнаковых чисел, так и для чисел со знаком (отличие — только в условиях, при которых считается, что наступилоарифметическое переполнение).

• Для кодирования действительных чисел используют 80-разрядное кодирование. При этом число предварительно преобразуется в нормализованную форму: 3,1415926 = 0,31415926 · 10 1 300 000 = 0,3 · 10 6 123 456 789 = 0,123456789 · 10 9 . Первая часть числа называется мантиссой, а вторая – характеристикой (порядком). Большую часть из 80 бит отводят для хранения мантиссы (вместе со знаком) и некоторое фиксированное количество разрядов отводят для хранения характеристики (тоже со знаком).

• Кодировка символов (часто называемая также кодовой страницей) – это набор числовых значений, которые ставятся в соответствие группе алфавитно-цифровых символов, знаков пунктуации и специальных символов.
Для кодировки символов в Windows используется таблица ASCII (American Standard Code for Interchange of Information).
В ASCII первые 128 символов всех кодовых страниц состоят из базовой таблицы символов. Первые 32 кода базовой таблицы, начиная с нулевого, размещают управляющие коды. Символы с номерами от 128 до 255 представляют собой таблицу расширения и варьируются в зависимости от набора скриптов, представленных кодировкой символов. Набор символов таблицы расширения различается в зависимости от выбранной кодовой страницы. Юникод (Unicode) — стандарт кодирования символов, позволяющий представить знаки практически всех письменных языков. Стандарт предложен в 1991 году некоммерческой организацией «Консорциум Юникода».

• В Unicode используются 16-битовые (2-байтовые) коды, что позволяет представить 65536 символов.

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

• Для представления символьных данных в кодировке Unicode используется символьный тип wchar_t.

2. Понятие о типах данных в C и C++. Базовые типы данных. Переменные в C и C++. Описание (объявление) переменных.

Тип данных — это показатель, позволяющий правильно интерпретировать выделенный объем памяти.

Основными типами данных являются:

назв. байт диапазон описание

bool 1 0 / 255 целочисл., 0 = false, 1-255 = true

char 1 0 / 255 целочисл., число указывает на символ

short 2 +-32767 целочисл.

int 4 -2 млн целочисл.

long 4 +-2 млн целочисл.

float 4 3.4*10^+-38 с пл. точкой, точность до 7 знаков

double 8 1.7*10^+-308 с пл. точкой, точность до 15 знаков

long double 8 1.7*10^+-308 с пл. точкой, точность до 15 знаков

Существуют дополнительные служебные слова signed и unsigned, указывающие на присутствие или отсутствие отрицательных чисел (знака) соответственно. Если отрицательных чисел нет, то диапазон отрицательных суммируется с диапазоном положительных.

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

Объявление переменных происходит путем указания типа данных, а затем — названия переменной. Объявленной переменной можно также в той же строке присвоить значение, поставив знак равенства и указав это значение. Имя переменной обязано начинаться с буквы.

3. Выражения в языке в C и C++. Основные операции. Понятие оператора в C и C++. Выражение и оператор присваивания.

Выражение в C/C++ — описания последовательности действий, приводящей к формированию значения определенного типа.

Операндами служат переменные одного и того же типа (или приведенные к одному и тому же типу).

Для произведения действий с операндами ставятся символы-операторы.

Операторы бывают унарными (действующими с одной переменной) и бинарными (действующими с двумя переменными).

-a унарный минус

a%b взятие остатка

++a префиксный инкремент

a++ суффиксный инкремент

—a префиксный декремент

a— суффиксный декремент

a =b больше или равно

a >b побитовый сдвиг справо

a+=b присваивание с суммированием (или любым другим действием)

a[b] обращение к элементу массива

*a непрямое обращение

a->b обращение к члену структуры

a.b обращение к члену структуры

Выражения с оператором присваивания «=» вида a=b+c позволяют присвоить правую часть выражения левой. Слева от оператора присваивания может стоять только одиночная переменная для присваивания в неё результата.

4. Массивы и указатели в C и C++. Имя массива, как идентификатор указателя. Присваивание для указателей. Оператор выделения новой памяти в C++. Понятие об утечки памяти, оператор удаления.

Указатели — это переменные, содержащие адрес некоторой области памяти.

Указатели определяют, как следует интерпретировать содержимое этой области.

Получение адреса: &a (получение адреса значения)

Разыменование: *a (получение значения по адресу)

Присваивание: b=*a; c=&b; и наоборот.

Новый участок памяти можно выделить при помощи оператора new, например:

При выделении памяти этот оператор генерирует конструктор класса с указанными элементами («5» в примере).

Любую динамически выделенную память (т.е. при помощи new) необходимо освобождать оператором delete для предотвращения утечки:

Утечка памяти — уменьшение объема памяти из-за неосвобожденных (ненужных) участков памяти или ошибок в программе.

Массив — это область памяти, в которой последовательно хранится несколько однотипных значений.

Массив инициализируется либо сразу с известным количеством значений:

int a[10]; //статический массив

либо с подстановкой переменной по необходимости:

int *a=new int[num]; //динамический массив

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

Данные в массив заносятся либо на этапе инициализации массива, например:

либо по необходимости отдельно в каждую ячейку:

Если массив сгенерирован динамически, после работы с ним необходимо освободить память: delete[] a;

5. Символьные строки в C и C++.

Для работы с символьными строками предусмотрен класс string, который в сущности представляет собой массив char[].

Стандартными функциями ввода-вывода являются scanf(«», ) и printf(«», переменные), позволяющие считывать форматированный текст.

При наличии класса iostream также для ввода-вывода можно использовать операторы cin и cout.

Для работы с переменными типа string применяются следующие функции:

• strlen длина строки

• atoi(c) перевод в целое число

• atof(c) перевод в число с пл. точкой

6. Оператор условного выполнения в C и C++.

В условии применяются операторы сравнения.

7. Метки и переходы в C и C++. Возможность организации цикла с помощью меток и переходов. Цикл в C и C++.

Переход к меткам:

Метки позволяют «перескакивать» в более раннюю или позднюю точку выполнения программы.

Илон Маск рекомендует:  Что такое код swfbutton >sethit

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

Цикл — это повторяющееся выполнение ряда инструкций.

Простейшая реализация цикла с метками:

int b=5; bool c=false;

if (c==true) goto a;

Более удобные реализации циклов в C++:

8. Потоки данных в C и C++. Файловые потоки, входной и выходной потоки программы. Функции открытия и закрытия файловых потоков. Функции ввода данных из потоков в C и C++. Преобразование данных при вводе.

Поток — это последовательность байтов. Поток может представлять содержимое файлов.

Потоки для работы с файлами создаются как объекты следующих классов:

ofstream — для вывода (записи) данных в файл;

ifstream — для ввода (чтения) данных из файла;

fstream — для чтения и для записи данных (двунаправленный обмен).

В общем случае оператор открытия потока будет иметь вид:

• всё ненулевое = 1; 0 = 0;

• Любой целый -> любой целый:

• при нехватке памяти старшие байты не добавляются;

• Любой целый -> любой действ.:

• дв. код меняется, число не меняется;

• Любой действ. -> любой целый:

• округление до ближайшего целого;

• Действ. с большей точн. -> действ. с меньшей точн.:

• лишние знаки после запятой отбрасываются.

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

11. Понятие функции в C и C++. Описание функций и обращение к ним. Обмен данными с функциями по значению и по ссылке. Прототипы функций. Заголовочный и исходный модули для описания функций. Область видимости переменных.

Функция (подпрограмма) — выделенный набор инструкций, выполнение которого производится по вызову этой функции по имени.

Функции, не возвращающие никаких значений, объявляются с типом данных void.

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

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

Простейшее создание и вызов функции:

void Function1() //создание безтиповой функции

int Fuction2(int a) //создание типовой функции

Function1(); //вызов безтиповой функции

int b=2; b=Function2(b); //иниц. переменной и присваивание типовой ф.

Возвращаемое значение в типовой функции указывается после оператора return. После этого оператора выполнение функции прекращается.

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

Существует два способа передачи параметров в функцию: по значению и по адресу.

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

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

void f(int i, int* j, int& k);

int i = 1, j = 2, k = 3;

Вызов структуры с указателем:

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

Членами структур могут быть функции.

13. Понятие класса и объекта. Уровни инкапсуляции членов класса. Перегрузка функций и операций в классах в C++. Конструкторы и деструкторы класса.

Объект — совокупность переменных и функций, часть из которых могут быть доступны из внешней программы по внешнему имени объекта и имени переменной/функции.

Функции объектов == методы.

Объект представляет какой-либо класс. Классы являются типами данных для объектов.

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

Уровни инкапсуляции определяют возможности доступа к переменным из внешней программы и при наследовании.

Public — доступ открыт всем, кто видит определение данного класса.

Private — доступ открыт самому классу (т.е. функциям-членам данного класса) и друзьям (friend) данного класса, как функциям, так и классам.

Protected — доступ открыт классам, производным от данного.

По умолчанию всегда private.

Синтаксис описания классов:

Синтаксис объявления объектов:

Обращение к объектам:

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

Описание прототипа класса (вне самого класса, например, в заголовочном модуле):

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

Инициализация с конструктором:

Деструктор — единственный в классе; срабатывает автоматически при удалении объекта, невозможно вызвать вручную.

Кодирование информации

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

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

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

Кодирование чисел

Числовую информацию компьютер обрабатывает в двоичной системе счисления. Таким образом, числа в компьютере представлены последовательностью цифр 0 и 1, называемых битами (бит – один разряд двоичного числа). В начале 1980-х гг. процессоры для персональных компьютеров были 8-разрядными, и за один такт работы процессора компьютер мог обработать 8 бит, т.е. максимально обрабатываемое десятичное число нс могло превышать 111111112 (или 25510). Последовательность из восьми бит называют байтом, т.е. 1 байт = 8 бит. Затем разрядность процессоров росла, появились 16-, 32- и, наконец, 64-разрядные процессоры для персональных компьютеров, соответственно возросла и величина максимального числа, обрабатываемого за один такт.

Использование двоичной системы для кодирования целых и действительных чисел позволяет с помощью 8 разрядов кодировать целые числа от 0 до 255, 16 бит дает возможность закодировать более 65 тыс. значений.

В ЭВМ применяются две формы представления чисел:

  • естественная форма, или форма с фиксированной запятой. В этой форме числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой, отделяющей целую часть от дробной, например +00456,78800; +00000,00786; -0786,34287. Эта форма неудобна для вычислений и применяется только как вспомогательная для целых чисел;
  • нормальная форма, или форма с плавающей точкой. В этой форме число выражается с помощью мантиссы и порядка как N = ±Μ • Р±r, где Μ – мантисса числа (|M|

Кодирование целых чисел

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

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

Пример. Порядок двоичного числа 000001101 равен 4, а мантисса – 1101.

В этой главе будут рассмотрены две группы методов кодирования целых чисел. Условно их можно обозначить так:

· Fixed + Variable (фиксированная длина экспоненты + переменная длина мантиссы)

· Variable + Variable (переменная длина экспоненты + переменная длина мантиссы)

1.1 Коды класса Fixed + Variable

В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит потребуется под запись мантиссы. Для кодирования целого числа необходимо произвести с числом две операции: определение порядка числа и выделение бит мантиссы (можно хранить в памяти готовую таблицу кодовых слов). Рассмотрим процесс построения кода данного класса на примере.

Пример. Пусть R = 15 – количество бит исходного числа. Отведем E = 4 бита под экспоненту (порядок), т.к. R≤2 4 . При записи мантиссы можно сэкономить 1 бит: не писать первую единицу, т.к. это всегда будет только единица. Таким образом, количество бит мантиссы меньше на один бит, чем количество бит для порядка.

Таблица 1 Код класса Fixed + Variable

число двоичное представление кодовое слово длина кодового слова
0010 0 0010 1
0011 00 0011 01 0011 10 0011 11
0100 000 0100 001 0100 010 … 0100 111 ..
0101 0000 0101 0001 … ..

1.2 Коды класса Variable + Variable

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

Таблица 2 Код класса Variable + Variable

число двоичное представление кодовое слово длина кодового слова
0 1
00 1 0 00 1 1
000 1 00 000 1 01 000 1 10 000 1 11
0000 1 000 0000 1 001 0000 1 010 …

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

Таблица 3 Гамма-код Элиаса

число кодовое слово длина кодового слова
01 0 01 1
00 1 00 00 1 01 00 1 10 00 1 11
000 1 000 000 1 001 000 1 010 …

Другим примером кода класса Variable + Variable является омега-код Элиаса (ω-код Элиаса). В нем первое значение (кодовое слово для единицы) задается отдельно. Другие кодовые слова состоят из последовательности групп длиной , начинающихся с единицы. Конец всей последовательности задается нулевым битом. Длина первой группы составляет 2 бита, длина каждой следующей группы равна двоичному значению битов предыдущей группы плюс 1. Значение битов последней группы является итоговым значением всей последовательности групп, т.е. первые групп служат лишь для указания длины последней группы.

Таблица 4 Омега-код Элиаса

число кодовое слово длина кодового слова
10 0 11 0
10 100 0 10 101 0 10 110 0 10 111 0
.. 11 1000 0 11 1001 0 … 11 1111 0 ..
.. 10 100 10000 0 10 100 10001 0 … 10 100 11111 0 ..
10 101 100000 0

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

Рассмотренные типы кодов могут быть эффективны в следующих случаях

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

2. Диапазон значений входных элементов не ограничен или неизвестен. Например, при кодировании 32-битовых чисел реально большинство чисел маленькие, но могут быть и большие.

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

1.3 Кодирование длин серий

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

Пример. Входную последовательность (общая длина 31бит) можно разбить на серии, а затем закодировать их длины.

000000 1 00000 1 0000000 1 1 00000000 1

Используем, например, γ-код Элиаса. Поскольку в коде нет кодового слова для нуля, то будем кодировать длину серии +1, т.е. последовательность 7 6 8 1 9:

7 6 8 1 9 Þ 00111 00110 0001000 1 0001001

Длина полученной кодовой последовательности равна 25 бит.

Метод длин серий актуален для кодирования данных, в которых есть длинные последовательности одинаковых бит. В нашем примере, если .

2. Некоторые теоремы ПОБУКВЕННОГО кодирования

В этом параграфе приведены некоторые теоремы о свойствах побуквенного кодирования.

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

позволяет следующим образом закодировать сообщение

Пример 2 Азбука Морзе. Входной алфавит – английский. Наиболее часто встречающиеся буквы кодируются более короткими словами:

А ® 01, В ® 1000, С ® 1010, D ® 100, E ® 0, …

Побуквенное кодирование задается таблицей кодовых слов: , , . Множество кодовых слов V=<βi> называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение следующим образом ,т.е. общий код сообщения складывается из элементарных кодов символов входного алфавита.

Количество букв в слове α=α1…αk называется длиной слова. (Обозначение |α|=k) Пустое слово, т.е. слово, не содержащее ни одного символа обозначается Λ. Если α=α1α2, то α1начало (префикс) слова α, α2окончание (постфикс) слова α.

Побуквенный код называется разделимым (или однозначно декодируемым), если любое сообщение из символов алфавита источника, закодированное этим кодом, может быть однозначно декодировано, т.е. если βi1 …βikj1…βjt , то k=t и при любых s=1,…,k is=js . При разделимом кодировании любое кодовое слово единственным образом разлагается на элементарные коды.

Пример. 3 Код из примера 1 не является разделимым, поскольку кодовое слово 010010 может быть декодируемо двумя способами: a3a3 или a2a1a2.

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

Пример 4. Код из примера 1 не является префиксным, поскольку элементарный код буквы a2является префиксом элементарного кода буквы a3.

Утверждение. Префиксный код является разделимым.

Доказательство(от противного). Пусть префиксный код не является разделимым. Тогда существует такая кодовая последовательность β, что она представлена различными способами из элементарных кодов: (побитовое представление одинаковое) и существует L такое, что при любом следует (βisjs) и it≠βjt), т.е. начало каждого из этих представлений имеет одинаковую последовательность элементарных кодов. Уберем эту часть. Тогда , т.е. последовательности элементарных кодов разные и существует β / , что βiLjLβ / или βjLiLβ / , т.е. βiL – начало βjL, или наоборот. Получили противоречие с префиксностью кода.

Заметим, что разделимый код может быть не префиксным.

Пример 5.Разделимый, но не префиксный код: A=<a,b>, B=<0,1>,

Приведем основные теоремы побуквенного кодирования.

Теорема (Крафт). Для того, чтобы существовал побуквенный двоичный префиксный код с длинами кодовых слов L1,…,Ln необходимо и достаточно, чтобы

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

Рисунок 2 Полное двоичное дерево с помеченными вершинами

В этом дереве выделим вершины, соответствующие кодовым словам. Тогда любые два поддерева, соответствующие кодовым вершинам дерева, не пересекаются, т.к. код префиксный. У i-того поддерева на r-том уровне – 2 r — Li вершин. Всего вершин в поддереве 2 r . Тогда , , .

Докажем достаточность утверждения. Пусть существует набор длин кодовых слов такой, что . Рассмотрим полное двоичное дерево с помеченными вершинами. Пусть длины кодовых слов упорядочены по возрастанию L1≤ L2≤ … ≤ Ln. Выберем в двоичном дереве вершину V1 на уровне L1. Уберем поддерево с корнем в вершине V1. В оставшемся дереве возьмем вершину V2 на уровне L2и удалим поддерево с корнем в этой вершине и т.д. Последовательности, соответствующие вершинам V1, V2,…, Vn образуют префиксный код. Теорема доказана.

Пример 6. Построить префиксный код с длинами L1=1, L2=2, L3=2 для алфавита A=<a1,a2,a3>. Проверим неравенство Крафта для набора длин

Неравенство выполняется и, следовательно, префиксный код с таким набором длин кодовых слов существует. Рассмотрим полное двоичное дерево с 2 3 помеченными вершинами и выберем вершины дерева, как описано выше. Тогда элементарные коды могут быть такими: a1 ®0, a2®10, a3 ®11.

Рисунок 3 Построение префиксного кода с заданными длинами

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

Теорема (МакМиллан). Для того чтобы существовал побуквенный двоичный разделимый код с длинами кодовых слов L1,…,Ln , необходимо и достаточно, чтобы .

Доказательство.Покажем достаточность. По теореме Крафта существует префиксный код с длинами L1,…,Ln, и он является разделимым.

Докажем необходимость утверждения. Рассмотрим тождество

Положим . Тогда тождество можно переписать следующим образом

где , – число всевозможных представлений числа j в виде суммы . Сопоставим каждому представлению числа j в виде суммы последовательность нулей и единиц длины j по следующему правилу

где bs – элементарный код длины s. Тогда различным представлениям числа j будут соответствовать различные кодовые слова, поскольку код является разделимым. Таким образом, и . Используя предельный переход получим при . Теорема доказана.

Пример 7. Азбука Морзе – это схема алфавитного кодирования

A®01, B®1000, C®1010, D®100, E®0, F®0010, G®110, H®0000, I®00, J®0111, K®101, L®0100, M®11, N®10, O®111, P®0110, Q®1101, R®010, S®000, T®1, U®001, V®0001, W®011, X®1001, Y®1011, Z®1100.

Неравенство МакМиллана для азбуки Морзе не выполнено, поскольку

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

3. оптимальное ПОБУКВЕННОЕ кодирование

3.1 Основные понятия

При кодировании сообщений считается, что символы сообщения порождаются некоторым источником информации. Источник считается заданным полностью, если дано вероятностное описание процесса появления сообщений на выходе источника. Это означает, что в любой момент времени определена вероятность порождения источником любой последовательности символов Р(x1x2x3. xL), L≥1. Такой источник называется дискретным вероятностным источником.

Если вероятностный источник с алфавитом А=<a1, a2, . an>порождает символы алфавита независимо друг от друга, т.е. знание предшествующих символов не влияет на вероятность последующих, то такой источник называется бернуллиевским. Тогда для любой последовательности x1x2. xL, L≥1, порождаемой источником, выполняется равенство:

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

Пусть имеется дискретный вероятностный источник без памяти, порождающий символы алфавита А=<a1,…,an> с вероятностями , . Основной характеристикой источникаявляется энтропия, которая представляет собой среднее значение количества информации в сообщении источника и определяется выражением (для двоичного случая)

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

Величина называется энтропией на символ последовательности длины L, где A L множество всех последовательностей длины Lв алфавитеA, x=(x1,x2. xL)последовательность Lбукв дискретного cтационарного источника. Обозначим через предел энтропии HLпри L® ¥ . Эту величину называют предельной энтропией источника.Показано, что для стационарного бернуллиевского источника

Для практических применений важно, чтобы коды сообщений имели по возможности наименьшую длину. Основной характеристикой неравномерного кода является количество символов, затрачиваемых на кодирование одного сообщения. Пусть имеется разделимый побуквенный код для источника, порождающего символы алфавита А=<a1,…,an> с вероятностями pi =P(ai), состоящий из n кодовых слов с длинами L1,…,Ln в алфавите <0,1>. Средней длиной кодового слова называется величина , которая показывает среднее число кодовых букв на одну букву источника.

Пример. Пусть имеются два источника с одним и тем же алфавитом А=<a1,a2,a3> и разными вероятностными распределениями P1=<1>, P2=<1>, которые кодируются одним и тем же кодом

Средняя длина кодового слова для разных источников будет различной

Lср(P1)=1/3 . 2 + 1/3 . 3 + 1/3 . 2= 7/3 ≈2.33

Lср(P2)=1/4 . 2 + 1/4 . 3 + 1/2 . 2= 9/4 =2.25

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

Избыточностью кода называется разность между средней длиной кодового слова и предельной энтропией источника сообщений

Избыточность кода является показателем качества кода, оптимальный код обладает минимальной избыточностью. Задача эффективного неискажающего сжатия заключается в построении кодов с наименьшей избыточностью, у которых средняя длина кодового слова близка к энтропии источника. К таким кодам относятся классические коды Хаффмана, Шеннона, Фано, Гилберта-Мура и арифметический код.

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

Теорема 1(Шеннон). Для источника с алфавитом А=<a1,…,an> и вероятностями pi =P(ai), и любого разделимого побуквенного кода средняя длина кодового слова всегда не меньше энтропии

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

Lcp 0 можно выбрать достаточно большое L, чтобы величина Lcp удовлетворяла неравенствам:

и левое неравенство для Lcp никогда не нарушается для разделимого кода.

Приведем некоторые свойства, которыми обладает любой оптимальный побуквенный код.

Доказательство (от противного): Пусть есть i и j, что Li>Lj при pi>pj. Тогда

т.е. если поменяем местами Li и Lj, то получим код, имеющий меньшую среднюю длину кодового слова, что противоречит с оптимальности кода. Лемма 1 доказана.

Лемма 2 Пусть – схема оптимального префиксного кодирования для распределения вероятностей Р, . Тогда среди элементарных кодов, имеющих максимальную длину, существуют два, которые различаются только в последнем разряде.

Доказательство. Покажем, что в оптимальной схеме кодирования всегда найдется два кодовых слова максимальной длины. Предположим обратное. Пусть кодовое слово максимальной длины одно и имеет вид , . Тогда длина любого элементарного кода не больше длины b, т.е. , . Поскольку схема кодирования префиксная, то кодовые слова не являются префиксом b. С другой стороны, b не является префиксом кодовых слов . Таким образом, новая схема кодирования также является префиксной, причем с меньшей средней длиной кодового слова , что противоречит оптимальности исходной схемы кодирования. Пусть теперь два кодовых слова и максимальной длины отличаются не в последнем разряде, т.е. , , , . Причем , не являются префиксами для других кодовых слов и наоборот. Тогда новая схема также является префиксной, причем , что противоречит оптимальности исходной схемы кодирования. Лемма 2 доказана.

3.2 Оптимальный код Хаффмана

Метод оптимального побуквенного кодирования был разработан в 1952 г. Д. Хаффманом. Оптимальный код Хаффмана обладает минимальной средней длиной кодового слова среди всех побуквенных кодов для данного источника с алфавитом А=<a1,…,an> и вероятностями pi =P(ai).

Рассмотрим алгоритм построения оптимального кода Хаффмана, который основывается на утверждениях лемм предыдущего параграфа.

Здесь символы источника уже упорядочены в соответствии с их вероятностями. Будем складывать две наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа. Тогда закодируем эти два символа 0 и 1. Далее кодовые слова достраиваются, как показано на рисунке 4.

a1 0.36 0.36 0.36 0.36 0.64 0

a2 0.18 0.18 0.28 0.36 0.36 1

Рисунок 4 Процесс построения кода Хаффмана

Таблица 5 Код Хаффмана

ai pi Li кодовое слово
a1 a2 a3 a4 a5 a6 0.36 0.18 0.18 0.12 0.09 0.07

Посчитаем среднюю длину, построенного кода Хаффмана

Lср(P)=1 . 0.36 + 3 . 0.18 + 3 . 0.18 + 3 . 0.12 + 4 . 0.09 + 4 . 0.07 =2.44,

при этом энтропия данного источника

H(p1,…,p6)= − 0.36 . log0.36 − 2 . 0.18 . log0.18 −

− 0.12 . log0.12 − 0.09 . log0.09 − 0.07log0.07=2.37

Рисунок 5 Кодовое дерево для кода Хаффмана

Код Хаффмана обычно строится и хранится в виде двоичного дерева, в листьях которого находятся символы алфавита, а на «ветвях» – 0 или 1. Тогда уникальным кодом символа является путь от корня дерева к этому символу, по которому все 0 и 1 собираются в одну уникальную последовательность (рис. 5).

| следующая лекция ==>
Цели развития социального знания в XXI веке | Алгоритм на псевдокоде

Дата добавления: 2020-02-07 ; просмотров: 193 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

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

Владельцы патента RU 2386168:

Системы и способы относятся к области кодирования произвольно распределенных признаков в объекте. Техническим результатом является снижение стоимости изготовления объектов с повышенной защищенностью данных. В изобретении определяют произвольно распределенные признаки объекта, сжимают и кодируют с помощью подписи. Создают ярлык, содержащий объект аутентификации и кодированные данные. Данные можно сжимать, определяя функцию плотности вероятности, связанную с объектом аутентификации. Векторы, связанные с произвольно распределенными атрибутами, определяют на основании, по меньшей мере частично, функции плотности вероятности. Векторы кодируют с использованием алгоритма арифметического кодирования. 5 н. и 24 з.п. ф-лы, 14 ил., 4 табл.

Область техники, к которой относится изобретение

Описанные здесь системы и способы, в целом, относятся к ярлыкам, защищенным от подделки и/или защищенным от незаконного изменения, и, в частности, для использования произвольно распределенных признаков объекта (внедренных или собственных) для ограничения несанкционированных попыток подделки или подлога с помощью ярлыка.

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

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

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

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

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

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

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

Краткое описание чертежей

Фиг.1 — пример объекта аутентификации для использования в качестве части ярлыка, например, сертификата подлинности.

Фиг.2 — схема, демонстрирующая пример системы сертификатов подлинности и иллюстративные процедуры, реализуемые системой для выдачи проверки сертификата подлинности.

Фиг.3А — схема иллюстративной системы сканирования для восприятия произвольно распределенных признаков объекта аутентификации, связанного с сертификатом подлинности.

Фиг.3В — вид сверху объекта аутентификации, показанного на фиг.3А.

Фиг.4 — логическая блок-схема иллюстративного процесса, который можно использовать для создания сертификата подлинности.

Фиг.5 — логическая блок-схема иллюстративного процесса, который можно использовать для сжатия данных, которые представляют произвольно распределенные атрибуты объекта аутентификации.

Фиг.6 — графическое представление областей, которые соответствуют четырем различным зонам в иллюстративном объекте аутентификации.

Фиг.7 — графическое представление девятнадцати разных зон иллюстративного объекта аутентификации.

Фиг.8 — график иллюстративной функции плотности вероятности для квадратного объекта аутентификации.

Фиг.9 — графическое представление областей в объекте аутентификации.

Фиг.10 — графическое представление, иллюстрирующее, как арифметический кодер кодирует строку «aba».

Фиг.11 — пример экземпляра объекта аутентификации, показанного с помощью узлов.

Фиг.12 — графическое представление сертификата подлинности, предназначенного для оптимизации эффективности затрат.

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

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

На фиг.1 показан пример объекта 100 аутентификации для использования как части ярлыка, например, сертификата подлинности. Для эффективного использования в сертификате подлинности объект 100 аутентификации обычно содержит произвольно распределенные признаки, которые являются уникальными и которые трудно копировать. Пример объекта 100 аутентификации, показанный на фиг.1, является частью сертификата подлинности на основе волокон и содержит волокна 110, внедренные в объект произвольным образом. Волокна 110 выступают в качестве произвольно распределенных признаков объекта 100 аутентификации. Волокна 110 могут быть включены в объект 100 аутентификации любыми средствами. Например, волокна 110 можно распылять на объект 100 аутентификации. Волокна 110 можно также внедрять в объект 100 аутентификации в процессе изготовления. Согласно одному варианту осуществления, волокна 110 являются оптическими волокнами, способными пропускать свет между своими концами. Таким образом, облучая светом определенную зону 120 объекта 100 аутентификации, освещают концы волокон 131-133, по меньшей мере, один конец которых находится в освещенной зоне.

Согласно фиг.1, объект 100 аутентификации содержит κ произвольно распределенных волокон. Объект 100 аутентификации можно сканировать с разрешением L×L пикселей. Каждое волокно имеет фиксированную длину R. Хотя иллюстративный объект 100 аутентификации, показанный на фиг.1, содержит волокна, следует понимать, что в сертификате подлинности аналогично можно использовать объекты аутентификации с другими произвольно распределенными признаками.

Произвольно распределенные признаки объекта 100 аутентификации можно использовать в сертификате подлинности для защиты доказательства подлинности произвольного объекта, например изделия. Например, определенные труднодублируемые данные вокруг произвольно распределенных признаков сертификата подлинности могут быть оцифрованы, подписаны личным ключом блока издания, и подпись может быть отпечатана на сертификате подлинности в машиносчитываемом виде для подтверждения подлинности изготовленного экземпляра. Каждый экземпляр сертификата подлинности связан с объектом, подлинность которого хочет проверить блок издания. Согласно одному варианту осуществления, проверка подлинности производится, осуществляется путем извлечения подписанных данных (данных о произвольно распределенных признаках) с использованием общего ключа блока издания и проверки совпадения извлеченных данных с данными соответствующего экземпляра сертификата подлинности. Чтобы подделать защищенные объекты, противнику необходимо по выбору: (i) вычислить личный ключ блока издания, (ii) разработать процесс изготовления, который может точно дублировать уже подписанный экземпляр сертификата подлинности, и (iii) завладеть подписанными экземплярами сертификата подлинности. С этой точки зрения сертификат подлинности можно использовать для защиты изделий, ценность которых, в целом, не превышает стоимость горячей штамповки одного экземпляра сертификата подлинности, включая накопленное развитие успешного процесса соперничающего изготовления.

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

Ниже будут рассмотрены иллюстративные аппаратные платформы для недорогого, но эффективного считывания произвольно распределенных признаков сертификата подлинности на основе волокон. Аппаратные платформы могут включать в себя штрих-код. Поскольку емкость штрих-кода для недорогих устройств считывания ограничивается примерно 3 кбитами, сообщение, подписанное личным ключом, ограничивается той же длиной. Кроме того, поскольку одной из целей сертификата подлинности является максимизация усилий противника, нацеленных на горячую штамповку конкретного экземпляра и сертификата подлинности, будет рассмотрена проблема, связанная с сохранением в подписанном сообщении фиксированной длины как можно большего объема информации об уникальных и произвольно распределенных признаках сертификата подлинности на основе волокон. Будет предоставлен пример аналитической модели сертификата подлинности на основе волокон. Затем в нижеследующем рассмотрении проблема сжатия множества точек будет также формализована и будет показано, что оптимальное сжатие позиций волокон в экземпляре сертификата подлинности является NP-полной задачей. Для эвристического решения этой задачи будет обеспечен алгоритм, который значительно повышает отношения сжатия по сравнению с традиционными методами сжатия.

II. Издание и проверка сертификата подлинности

На фиг.2 показана схема, демонстрирующая иллюстративную систему 200 сертификата подлинности и иллюстративные процедуры, используемые системой для издания и проверки сертификата подлинности. Система 200 сертификата подлинности включает в себя сертификат 210 подлинности, блок 320 издания и блок 250 проверки. Согласно фиг.2, сертификат 210 подлинности может содержать объект 100 аутентификации, показанный на фиг.1, штрих-код 213 и текст 215.

Информация, которую нужно защищать на сертификате подлинности, включает в себя: (а) представление труднодублируемых произвольно распределенных признаков объекта 100 аутентификации и (b) связанные с ним произвольные текстовые данные. Сначала произвольно распределенные признаки объекта 100 аутентификации, например позиции волокон, сканируют с использованием аппаратного устройства. Ниже со ссылкой на фиг.3 мы подробно рассмотрим, как собирают и представляют эту информацию.

В целях рассмотрения предположим, что результирующая информация f является случайной строкой из nF битов. Параметр nF является фиксированным и равен nF =k·nRSA, k∈N, где nRSA — это длина общего ключа RSA (например, nRSA = 1024), и k обычно задано как k ∈ [1,3]. При данном nF собрание f данных 231, представляющее произвольно распределенные признаки объекта 100 аутентификации, может статистически максимизировать расстояние между двумя различными экземплярами сертификата подлинности. Эта задача непосредственно сводится к минимизированному правдоподобию ложного отрицательного результата и ложного положительного результата на этапе проверки.

Текстовые данные f являются произвольной строкой символов, которая зависит от приложения (например, срока годности, гарантии производителя). Текстовые данные извлекаются из текста 215, напечатанного на сертификате 210 подлинности, как показано на фиг.2.

Текстовые данные можно хэшировать с использованием криптографически защищенного алгоритма 237 хэширования, например SHA1. Выход хэш-функции обозначается как сообщение t, состоящее из nT битов. Блок 230 издания создает сообщение m, которое может быть подписано RSA. Например, сообщения f и t сливаются в сообщение m длиной nM = nF с использованием обратимого оператора ⊗, который гарантирует, что каждый бит из m зависит от всех битов из f и t. Этот этап может максимизировать число битов, которыми нужно манипулировать в данных 231, а также в тексте 215 для создания определенного сообщения m. Примером такого оператора является симметричное шифрование m = t ⊗ f = Et(f) для f с использованием t или определенного подмножества битов из t в качестве ключа. Сообщение m подписывается подписью 235 RSA с использованием личного ключа 233 блока 230 издания. Каждые nRSA битов из m подписываются по отдельности. Результирующая подпись s имеет nS = nM = nF битов. Это сообщение кодируется и печатается как штрих-код 213 (например, штрих-код по стандарту PDF417) на сертификате 210 подлинности.

Проверка сертификата 210 подлинности производится в несколько этапов. Блок 250 проверки сначала сканирует отпечатанные компоненты: текст 215 и штрих-код 213. Штрих-код 213 декодируют в первоначально отпечатанную подпись s. Текст 215 сканируют и хэшируют для создания сообщения t. Заметим, что для этой задачи не требуется общий процесс оптического распознавания символов (OCR), поскольку шрифт, используемый для печати текста, известен блоку 250 проверки и оптимизирован для усовершенствованного OCR. Для успешной проверки сертификата подлинности текст 215 и штрих-код 213 должны быть считаны без ошибок; современные технологии сканирования позволяют легко выполнить эту задачу.

Блок 250 проверки осуществляет проверку 255 подписи RSA на s с использованием общего ключа 253 блока издания и получает подписанное сообщение m. Затем блок 250 проверки может вычислить f=m(⊗) -1 t. В примере использования шифрования в качестве ⊗ это достигается дешифрованием f=Et -1 (m). Затем блок 250 проверки сканирует данные 251, представляющие произвольно распределенные признаки в объекте 100 аутентификации, и создает их представление f’. Блок 250 проверки сравнивает f’ с извлеченным f. Блоку 250 проверки нужно определить величину корреляции между двумя множествами данных: одним — присоединенным к сертификату, и другим — используемым для создания подписи на сертификате подлинности. На блоке 259 принятия решения, если уровень подобия двух множеств данных превосходит некоторый порог, то блок 250 проверки объявляет, что этот сертификат 210 подлинности подлинный, и наоборот.

На фиг.3А показана схема иллюстративной системы 300 сканирования для восприятия произвольно распределенных признаков объекта 310 аутентификации, связанных с сертификатом подлинности. Система 300 сканирования содержит оптический датчик 322 и источник 324 света. Оптический датчик 322 способен сканировать объект 310 аутентификации и может содержать матрицу устройств с зарядовой связью (ПЗС) с конкретным разрешением. Согласно одному варианту осуществления, оптический датчик 322 имеет разрешение 128×128 пикселей. Источник 324 света способен обеспечивать свет определенной длины волны для освещения зоны аутентификации объекта 310. Источник 324 света может включать в себя, например, светодиод (СИД). Согласно фиг.3А, один конец волокна 326 объекта 310 аутентификации освещается источником 324 света. Свет проходит к другому концу волокна 326 и воспринимается оптическим датчиком 322.

На фиг.3В показан вид сверху объекта 310 аутентификации, показанного на фиг.3А. В ходе работы система 300 сканирования делит объект 310 аутентификации на зоны, например зоны 311-314. Согласно фиг.3В, источник 324 света системы 300 сканирования излучает свет на зону 314, тогда как зоны 311-313 изолированы от источника 324 света. Благодаря освещению зоны 314 оптический датчик 322 может определить местоположение концевых точек в зонах 311-313 объекта 310 аутентификации. Таким образом, считывание произвольно распределенных признаков в объекте 310 аутентификации включает в себя четыре цифровых изображения, которые содержат четыре разных множеств точек. Каждое множество точек связано с конкретной зоной и определяется путем освещения этой зоны.

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

На фиг.4 показана логическая блок-схема иллюстративного процесса 400, который можно использовать для создания сертификата подлинности. В блоке 405 сканируют объект аутентификации в сертификате подлинности. Объект аутентификации можно сканировать с использованием системы 300, показанной на фиг.3А.

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

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

В блоке 420 кодируют сжатые данные. Например, сжатые данные можно подписывать с использованием личного ключа 233, показанного на фиг.2. В блоке 425 кодированные данные включают в сертификат подлинности. Например, кодированные данные можно напечатать в сертификат подлинности в виде штрих-кода, например штрих-кода 213, показанного на фиг.2.

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

В блоке 505 определяют функцию плотности вероятности, связанную с объектом аутентификации. Функция плотности вероятности будет рассмотрена в разделе III-A. Функция плотности вероятности показана в уравнении 11. На фиг.8 показано графическое представление иллюстративной функции плотности вероятности. В общих чертах функция плотности вероятности выражает вероятность того, что единица произвольно распределенных атрибутов находится в определенном месте объекта аутентификации. Применительно к сертификату подлинности на основе волокон функция распределения вероятности может выражать вероятность того, что конкретная точка в зоне объекта аутентификации освещена. Функцию плотности вероятности также можно использовать для вычисления количества волокон, освещаемых в конкретной зоне.

В блоке 510 определяют векторы, связанные с произвольно распределенными атрибутами. Применительно к сертификату подлинности на основе волокон используются двухточечные векторы, и это будет рассмотрено в разделе IV-A. В частности, уравнение 16 можно использовать для вычисления двухточечных векторов для выражения произвольно распределенных атрибутов в сертификате подлинности на основе волокон.

В блоке 515 векторы кодируют с использованием алгоритма арифметического кодирования. Алгоритм арифметического кодирования будет рассмотрен в разделе IV-A. Иллюстративный алгоритм показан в таблице 2.

В блоке 520 определяют путь для сжатия части векторов в фиксированном объеме данных. Способ вычисления пути рассмотрен в разделе IV-B. Иллюстративный путь можно вычислить с использованием уравнения 20. В блоке 525 возвращают путь сжатых данных, выражающий часть произвольно распределенных атрибутов.

III. Модель сертификата подлинности

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

А. Распределение освещенных концевых точек волокон

Объект (L,R,K) аутентификации моделируется как квадрат со стороной L единиц и К волокнами фиксированной длины R ≤ L/2, произвольно разбросанных по объекту. Из этой модели можно вывести другие варианты модели, например объект с переменной длиной волокна или объект произвольной формы. Объекты аутентификации располагаются в положительном квадранте двухмерной прямоугольной системы координат, как показано на фиг.1. Кроме того, объект аутентификации делят на четыре равных квадрата S=1,S2,S3,S4>. Затем каждый из них используют для записи трехмерной структуры волокон, как описано выше со ссылкой на фиг. 3А и 3В. Затем волокно обозначают как упорядоченную пару f= точек A,B⊂S, причем расстояние между ними .

Определение 1. Распределение освещенных концевых точек волокон

Пусть один из квадратов Si освещен, тогда функция плотности вероятности (ФПВ) φ(i,Q(x,y)) определяется для любой точки Q(x,y) ⊂ S-Si через вероятность ξ(i,P) того, что область P⊂S-Si содержит освещенную концевую точку А волокна f= при условии, что другая концевая точка В располагается в освещенной зоне Si. Более формально для любой P ⊂ S — Si

Предположим, что бросание волокна f= в объект аутентификации состоит из двух зависимых событий: (i) первая концевая точка А попадает в объект аутентификации, и (ii) вторая концевая точка В достигает объекта аутентификации. Хотя А может попасть в любое место СП (сертификата подлинности), позиция В зависит от местоположения А. Концевая точка В должна попасть на часть периметра круга с центром в А и радиусом R и содержащегося в объекте аутентификации. В оставшейся части этой подобласти функцию φ(i,Q(x,y)) аналитически вычисляют на основании анализа событий (i-ii). Для краткости для случая, когда освещена зона S1, вычисляется только φ(1,Q(x,y)). φ(1,Q(x,y)) вычисляется в два этапа.

Определение 2. Ограничение периметра

Во-первых, для данной точки A ⊂ S определяют функцию ρ(A), которая выражает длину части периметра (дуги) круга с центром в А и радиусом R, который целиком заключен в объекте S аутентификации. В объекте аутентификации имеется четыре разных зоны (обозначенные P1-P4 на фиг.6), где ρ(A) однородно вычисляется.

На фиг.6 изображено графическое представление областей P1-P4, соответствующих четырем различным зонам в иллюстративном объекте 600 аутентификации. Для каждой точки в определенной области Рх вычисляют функцию ограничения периметра с использованием замкнутой аналитической формы, характерной для этой области, с использованием уравнений 7-10, которые рассмотрены ниже.

Это центральная область объекта аутентификации, где для любой точки Q ⊂ P1 окружность радиуса R с центром в Q не пересекается ни с какими сторонами объекта аутентификации. Границы области заданы следующим образом: R ≤ x ≤ L-R, R ≤ y ≤L-R.

ρ(Q(x,y))=2Rπ. (7)

Имеется четыре разных зоны Р2, где окружность радиуса R с центром в любой точке Q ⊂ P2 дважды пересекается с одной и той же стороной объекта аутентификации. Для краткости рассмотрим только следующий случай:

R ≤x ≤ L-R, 0 ≤ y 2 + y 2 ≥ R 2 .

Имеется четыре разных зоны Р3, где окружность радиуса R с центром в любой точке Q ⊂ P4 по одному разу пересекается с двумя краями СП. Рассмотрим только следующий случай: x 2 +y 2 2 .

Во всех уравнениях 8-10 фактическая φ(1,Q(x,y)) вычисляется исходя из того, что освещенная концевая точка А волокна f= находится в позиции A=Q(x,y), только если В находится на части(ях) окружности C(Q,R) с центром в Q(x,y) с диаметром R и содержащейся в S1.

Лемма 3. Зависимость φ(i,Q(x,y)) от ρ(Q(x,y)).

Используя функцию ρ(Q(x,y)), вычисляют ФПВ φ(i,Q(x, y)) с использованием следующего интеграла:

где ϑ описывает периметр C(Q,R)⊂S и α является константой, так что:

Точка Q⊂S-Si может быть освещена только благодаря волокну f=, так что

B⊂Si. Отсюда следует, что В расположена где-то на периметре круга C(Q, R), содержащегося в Si. Для данного волокна f= вероятность того, что А лежит на конкретной бесконечно малой дуге длиной dl⊂S, равна dl/ρ(B). Следовательно:

где функция area(S-Si) вычисляет площадь под S-Si. Таким образом, ФПВ φ(1,Q(x,y)) в точке Q⊂S-S1 пропорциональна интегралу от величины, обратной ρ(•), по C(Q,R)⊂S1.

На фиг.7 показано графическое представление девятнадцати различных зон иллюстративного объекта 700 аутентификации, которые имеют характерные аналитические формулы в качестве решения интеграла, приведенного в уравнении 11. Для простоты φ(1,Q(x,y)) приблизительно решается с использованием простого численного расчета. Результаты приведены на фиг.8.

На фиг.8 показан график иллюстративной функции плотности вероятности для квадратного объекта аутентификации с параметрами L=64 и R=28, дискретизированной в единичных точках. На фиг.8 показано, что вероятность того, что концевая точка волокна лежит в определенной малой области P⊂S-Si, значительно изменяется в зависимости от конкретного положения Р в S-Si. Используя информацию об изменении φ(i,Q(x,y)) в пределах S-Si, можно значительно усовершенствовать алгоритмы сжатия подмножества точек, что представлено в разделе IV. Изготовление объекта аутентификации, характеризуемого φ(i,Q(x,y))=const по всей области S-Si, является нетривиальной задачей, вероятно, столь же сложной, как и горячая штамповка оригинального объекта аутентификации.

В. Отношение освещенности концевых точек волокна

Определение 3. Отношение освещенности концевых точек волокна

Для объекта аутентификации (L,R,K) и его освещенной зоны Si отношение освещенности λ определяется как вероятность того, что волокно f= легло так, что одна из его концевых точек находится в B⊂S-Si, при том условии, что другая его концевая точка находится в A⊂Si:

λ=Pr[B⊂S-S i |f=,A⊂S i ] (14)

Определение 4. Возможно освещенная дуга

Для любой точки A⊂Si определяют функцию ψ(i,A(x,y)), которая измеряет длину части периметра C(A,R), содержащегося в S-Si.

На фиг.9 показано графическое представление областей T0-T8, где ψ(i,Q(x,y)) вычисляется с использованием характерных замкнутых аналитических форм. ψ(i,Q(x,y)) аналитически вычисляют на основании анализа событий (i-ii) из раздела III-A. По аналогии с разделом III-A вычисление производится только в случае, когда зона Si освещена. В СП имеется девять различных зон (обозначенных Т0-Т8 на фиг.9), где ψ(1,Q) вычисляется однородно. Аналитические замкнутые формы для ψ(1,Q), зависящие от местоположения Q в Si, приведены в таблице 1.

Лемма 4. Зависимость ψ(1,Q(x,y)), ρ(Q(x,y)) и λ.

Отношение освещенности, определенное в определении 3, можно вычислить следующим образом:

Круг с центром в точке A⊂S и радиусом R обозначен C(A,R). Для каждой точки Q⊂Si вероятность того, что другая концевая точка В волокна f= лежит в S-Si, равна отношению длин частей периметра C(Q,R), содержащихся в S-Si и S соответственно. Интегрируя это отношение по всем точкам в Si, получаем уравнение 15.

С учетом того, что объект аутентификации (L,R,K) с использованием λ вычислен путем численной аппроксимации уравнения 15 и замкнутых форм для ψ(1,Q) и таблицы 1, можно вычислить ожидаемое число освещенных точек в S-Si, когда Si освещена как λK/2. Например, для объекта аутентификации (64,28,100) результирующее λ ≈ 0.74, и это значит, что в среднем число освещенных концевых точек в случае, когда Si освещена, составляет примерно 0.74×50 = 37.

IV. Сжатие подмножества точек в СП

Цель системы сертификата подлинности состоит в том, чтобы задача изготовления (т.е. горячей штамповки) конкретного экземпляра объекта аутентификации была как можно труднее. Эта цель количественно выражается в необходимости записи позиций как можно большего количества волокон объекта аутентификации. В иллюстративном алгоритме сжатия количество зон объекта аутентификации равно четырем; поэтому для каждой зоны Si четверть nM/4 битов подписанного сообщения m выделяется для сохранения как можно большего количества концевых точек волокон, освещенных в S-Si, когда свет падает на Si. Заметим, что в общем случае не все освещенные точки нужно сохранять; кодировать с использованием nM/4 битов можно только наибольшее подмножество этих точек.

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

А. Кодирование двухточечных векторов

В этом подразделе мы опишем, как вектор, заданный своими начальной и конечной точками, кодируется с использованием количества битов, близкого к минимальному. Дополнительное ограничение состоит в том, что точки в рассматриваемой области появляются в соответствии с данной ФПВ.

1) Арифметическое кодирование

Арифметический кодер (АК) преобразует входной поток произвольной длины в единичное рациональное число в [0,1>. Главная сила АК в том, что он может сжимать как угодно близко к энтропии. Ниже мы покажем, как слово «aba» кодируется с использованием алфавита с неизвестной ФПВ появления символов.

На фиг.10 показано графическое представление примера того, как арифметический кодер кодирует строку «aba» с использованием алфавита L= с неизвестной ФПВ появления символов. Пример показан на фиг.10.

Первоначально диапазон АК сбрасывают на [0,1> и каждому символу в L назначают равную вероятность появления Pr[a]=Pr[b]=1/2. Таким образом, АК делит свой диапазон на два поддиапазона [0,0.5> и [0.5,1>, каждый из которых представляет «b» и «a» соответственно. Символ “а” кодируется сужением диапазона АК до диапазона, соответствующего этому символу, т.е. [0.5,1>. Кроме того, АК обновляет счетчик появления символа “а” и повторно вычисляет Pr[a]=2/3 и Pr[b]=1/3. В следующей итерации, согласно обновленным Pr[a], Pr[b], АК делит свой диапазон на [0.5,0.6667> и [0.6667,1>, каждый из которых представляет «b» и «a» соответственно. При следующем появлении «b» АК сужает свой диапазон до соответствующего [0.5,0.6667>, обновляет Pr[a]=Pr[b]=2/4 и делит новый диапазон на [0.5,0.5833> и [0.5833,0.6667>, каждый из которых представляет «b» и «a» соответственно. Поскольку последним символом является «a», АК кодирует этот символ, выбирая в качестве выходного значения любое число в [0.5833,0.6667>. Выбирая число, которое кодируется минимальным числом битов (в нашем примере, цифр), 0.6, АК создает свое окончательное выходное значение. Декодер воспринимает длину сообщения либо явно в заголовке сжатого сообщения, либо в особом символе “конец файла”.

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

АК кодирует последовательность входящих символов s=s1,s2. с использованием количества битов, равного энтропии источника, . Поэтому для полубесконечного потока независимых и одинаково распределенных символов на компьютере с арифметикой бесконечной точности АК является оптимальным энтропийным кодером.

Арифметическое кодирование двухточечного вектора с минимальным расстоянием

Пусть свет падает на один из квадрантов Si объекта аутентификации (L,R,K). Затем предположим, что объект аутентификации разделен на сетку из L×L единичных квадратов U=u(i,j), i=1. L, j=1. L, где каждый u(i,j) покрывает квадратную область в x∈u с координатами (x,y).

Лемма 5. Вероятность освещения единицы.

Если предположить, что имеется κ волокон, имеющих в точности одну концевую точку в S-Si, вероятность того, что единичная область u(x,y)⊂S-Si содержит, по меньшей мере, одну освещенную концевую точку волокна, равна:

r(u)=Pr[(∃f=∈F)A⊂u,B⊂Si]=1-[1-ξ(i,u)] κ (16)

Из уравнения 7 выводится уравнение 16. В разделе III-B вычисляется ожидание для κ, равное E[κ]=λK/2.

Задача I. Двойное векторное кодирование для СП

При том условии, что единица u⊂S-Si содержит освещенную концевую точку волокна, задача состоит в том, чтобы кодировать с использованием как можно меньшего числа битов местоположения двух других освещенных единиц v1 и v2 относительно единицы u. Дополнительное ограничение состоит в том, что среди всех освещенных единиц в S-Si главные точки v1 и v2, Q1 и Q2 соответственно располагаются на двух кратчайших расстояниях в евклидовом смысле от главной точки u, Q u . Правило приоритетов установлено таким образом, что если множество единиц V, |V|> 1 находится на одном и том же расстоянии по отношению к u, то та из них, которая имеет наибольшую вероятность освещения: argmaxν∈V(τ(ν)), кодируется первой.

Кодирование вектора от единицы к единице производится с использованием АК, который использует алгоритм А1 для назначения соответствующего диапазона на интервале кодирования каждому символу кодирования, т.е. каждой единице ν⊂S-S i, отличной от исходной единицы u. Для каждой единицы v алгоритм А1 назначает диапазон, равный вероятности того, что v является одной из двух ближайших освещенных единиц относительно исходной единицы u. Эта вероятность обозначается как p(ν|u). В случае, когда ожидается, что κ>>1 единиц освещены в S-S i , p(ν|u) можно вычислить следующим образом:

где множество единиц M v (u) вычисляется, как в алгоритме 1. Для каждой единицы ν алгоритм А1 назначает диапазон γ(y,v), используемый АК для кодирования, с тем условием, что u уже закодирована. Этот диапазон равен:

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

Двойное векторное кодирование используется как примитив для кодирования подмножества точек во всем алгоритме сжатия, представленном в разделе IV-B. Хотя алгоритм кодирования близок к оптимальному для множества предположений, представленных в разделе IV-A.2, то же самое множество ограничений не пригодно для задачи сжатия в целом, поэтому в разделе IV-B рассматривается внутренняя оптимальность использования арифметического кодирования в диапазоне выделения через А1.

В. Сжатие подмножества точек

Рассмотрим модель задачи оптимизации для сжатия позиций как можно большего количества освещенных единичных областей с использованием фиксированного числа битов. Рассмотрим следующий ориентированный полный граф со взвешенными ребрами. Для каждой освещенной единицы u⊂S-Si создается узел nu. Ориентированное ребро e(u,ν) от узла nu к узлу nν взвешено оптимальной длиной кодового слова, которое кодирует вектор, указывающий на v, ω(e(u,ν))=-log2[γ(ν,u)], как в уравнении 19, при том условии, что u уже закодирована. Обозначим этот граф как G(N,E,Ω), где N, E и Ω представляют множество узлов, ориентированных ребер и соответствующих весовых коэффициентов соответственно.

Задача 2. Сжатие подмножества точек (СПТ)

ДАНО: ориентированный, полный и взвешенный граф G(N,E) с неотрицательной вершинной функцией Q: ER, положительное целое l min ∈ Z + , положительное действительное число Λ∈R + .

ВОПРОС: существует ли подмножество из l > l min узлов N * ⊂N с путем через них, т.е. перестановка * π(1) . n * π(l) >, так что сумма весовых коэффициентов вдоль пути равна:

Задача 2 моделирует задачу оптимизации для сжатия как можно большего количества (т.е. l) концевых точек волокна в объекте аутентификации с использованием фиксированного хранилища (т.е. А). Эта задача является NP-полной, поскольку можно показать, что асимметричную задачу коммивояжера, АЗК, можно свести к СПТ, путем двоичного поиска по А. В остальной части этого раздела представлена конструктивная эвристика А2, нацеленная на решение этой задачи. Главное конструктивное требование для эвристики состоит в высокой производительности во время выполнения, поскольку каждый сертификат подлинности нужно подписывать отдельно на производственной линии.

Во-первых, мера расстояния между двумя узлами в N не подчиняется неравенству треугольника для всех узлов. Интуитивно, процедура кодирования из раздела IV-A кодирует векторы в S-S i с использованием количества битов, пропорционального вероятности того, что определенная единица является одной из двух ближайших освещенных точек. Поэтому единицы, более далекие от исходного узла, кодируются значительно более длинными кодовыми словами, поскольку они, скорее всего, не появляются, из-за чего быстрые переходы к этим узлам в решении являются крайне нежелательными.

Теорема 2. Мера ω расстояния не всегда удовлетворяет неравенству треугольника:

Для простоты предположим, что (∀u⊂S-S i ), t=τ(u)=const, тогда u, ν, и w располагаются вдоль одной линии в S-S i . Эвклидовы расстояния ||y-ν||, ||ν-w||, и ||y-w|| равны a, b, и a+b соответственно. Из неравенства треугольника следует, что f(u,ν,w)=log 2 [γ(w,u)]-log 2 [γ(ν,u)]-log 2 [γ(w,ν)]≥0. Из уравнений 17 и 18 можно вывести:

и показать, что для abπt>>1 неравенство треугольника не выполняется, т.е. f(a,b,t) 1, могут быть решены с результатом, в худшем случае, в (3µ+1)µ/2 хуже оптимального решения. Метрика расстояний ω не подчиняется этому ограничению, поэтому эвристика для задачи 2 разработана без гарантии на худший случай. Можно разместить экземпляр объекта аутентификации, который нельзя удовлетворительно сжать. Вероятность этого события должна быть мала, менее одного на миллион.

Предпосылкой использования метрики расстояний ω из раздела IV-A является предположение, что хорошее решение обеспечивает прохождение через каждый узел на своем маршруте через два ближайших соседних узла. Поэтому в рамках задачи 2 используемая метрика является оптимальной, только если наилучшее найденное решение удовлетворяет этому свойству. Если конечное решение не имеет этого свойства, оптимальность кодирования единичного вектора зависит от распределения весовых коэффициентов ребер в решении.

Разработанная эвристика А2 имеет две стадии: конструктивную фазу и фазу итеративного усовершенствования. Конструктивная фаза подчиняется жадной эвристике, которая строит первоначальное решение. Сначала А2 идентифицирует множество доминирующих ребер E′. Для каждой пары ребер e(u,ν), e(ν,u) между узлами u, ν, А2 выбирает только более короткое из двух и сохраняет его в E′. Затем создается множество Р из первоначальных подпутей путем сортировки ребер в E′ и выбора К кратчайших ребер, для которых сумма весовых коэффициентов как можно ближе к Λ. Первый и последний узел в пути p i обозначаются как s i и d i соответственно. На следующем этапе А2 присоединяет подпути из Р итеративно в порядке возрастания их весовых коэффициентов: в любой точке пара кратчайших подпутей p i , pj, имеющих общий начальный-конечный узел d i =s j , связывается, пока не будут созданы все возможные соединения. В маловероятном случае, когда |P|=1, находится оптимальное решение, и поиск останавливается. В противном случае все однореберные подпути удаляются из Р. Затем с использованием алгоритма Дейкстры А2 находит все кратчайшие пути между каждым конечным хвостом di каждого подпути p i в Р и начальными хвостами всех остальных подпутей s j , i=1. |P|, i≠j. Кратчайшие пути обходятся через узлы, не принадлежащие Р. Кратчайший путь между s i и d j обозначается как q(i,j). На другом жадном этапе А2 сортирует все сочленения pi |q(i,j)|p j по их отношению вес/счетчик узлов. В порядке возрастания этой метрики А2 продолжает присоединять подпути в Р через узлы в N-P, пока суммарное количество оставшихся путей не станет равным |P|=maxP (обычно maxP=9). Оставшиеся пути присоединяются с использованием точного алгоритма, который находит путь p h с оптимальной метрикой: максимальной мощностью и суммой весов, меньшей А. На конечном этапе процедура повторного обхода просматривает все узлы в Р и, используя алгоритм Дейстры, пытается найти кратчайшие пути к другим узлам в Р через оставшиеся узлы в Е. Та же процедура также пытается найти лучший конечный хвост, чем тот, который существует в p h . Для каждого повторного обхода А2 проверяет, имеет ли новый повторный обход лучшую метрику, чем текущий, наилучший путь p h . На фиг.11 показан пример экземпляра объекта аутентификации (512,0.4 . 512,256), в котором имеется κ = 88 узлов. А2 возвратил путь, показанный жирными линиями. Путь таков, что его сумма весовых коэффициентов меньше Λ = 512. Для документирования пути используется 12.11 битов на точку.

На фазе итеративного усовершенствования мы несколько раз повторяем следующий цикл. На первом этапе А2 стягивает наилучший найденный к настоящему моменту путь p лучш в p h , так что |p h| максимален, и сумма весовых коэффициентов вдоль p h меньше доли ρΛ. Параметр стягивания ρ произвольно выбирают в каждой итерации в p ∈ <0.4,0.8>. Узлы n и n l обозначены как первый и последний узел в p h. Хотя сумма весовых коэффициентов в p h меньше Λ, среди ребер, которые имеют n или n l в качестве конечного или начального узла соответственно, находим ребро е с минимальным весом присоединяем его к p h . Когда новый путь-кандидат ph создан, его принимают как наилучшее решение, если его метрика лучше метрики наилучшего пути, созданного до сих пор. На последнем этапе цикла итеративного усовершенствования А2 осуществляет вышеописанную процедуру повторного обхода.

Для приспособления времени прогона А2 для конкретного класса объектов аутентификации (L,R,K) в пределах одной секунды цикл усовершенствования повторяется I = <100,10000>раз. В целом, сложность А2 в наихудшем случае составляет O(|N| 3 log|N|), когда кратчайшие пути с множественными источниками вычисляются посредством алгоритма Дейкстры. В реализации, которая использует алгоритм Флойда-Варшалла для вычисления всех пар кратчайших путей, сложность А2 можно снизить до O(|N| 3 ). Хотя граф изначально полон, удаляя ребра с высокими весовыми коэффициентами, мы создаем разреженный граф, где алгоритм Джонсона для кратчайших путей всех пар дает O(|N| 2 log|N|+|N||E|).

V. Эмпирическая оценка

В этом разделе показано, как параметры объекта аутентификации (L,R,K) влияют на производительность алгоритма А.2. На фиг.11 показано решение для одного варианта этой задачи, объекта аутентификации (512,0.4 . 512,256). Сетка сканирования до L=512 ячеек сканирования. На чертеже описан случай, когда освещен нижний левый квадрант объекта аутентификации. Граф G(N,E), построенный с использованием соответствующих освещенных концевых точек волокна, показан линиями средней толщины. Показаны только десять кратчайших ребер, начинающихся с каждого из κ = 88 узлов графа. Результирующий путь, показанный на чертеже с использованием толстых линий, состоит из 41 точек. Сумма весовых коэффициентов вдоль ребер пути меньше лимита хранилища: А = 512 бит. Путь сжимается с использованием 12.11 битов на концевую точку волокна (б/ктв). Сохранение данных без сжатия потребовало бы 41 . 18=738 битов, что дает коэффициент сжатия 0.61. Коэффициент сжатия определяется как отношение размера сжатого сообщения к размеру исходного сообщения.

VI. Цель проектирования для системы СП

Целью разработчика сертификата подлинности является максимизация стоимости горячей штамповки ζf с использованием ограниченной стоимости изготовления ζm. На ζm может влиять несколько параметров. Для краткости и простоты рассмотри три параметра:

суммарная длина волокна RK ≤ Φ,

допуск сканирования ζ и

хранилище штрих-кода Λ.

Производительность системы оптимизируется путем ограничения количества попыток, доступных противнику, для точного позиционирования достаточного подмножества подписанных концевых точек волокна (раздел VI-A) и выбора параметров системы * ,K *>, так что ожидаемая стоимость горячей штамповки ζ f (A2) достигает максимума (раздел VI-B).

А. Ограничение количества вражеских попыток

Рассмотрим схему сжатия С, которая сохраняет G из κ освещенных концевых точек волокна в хранилище, ограниченном по Λ. В общем случае при горячей штамповке сертификата подлинности противник может использовать все κ волокон для размещения, по меньшей мере, Gζ из них точно в их соответствующих местах. Стоимость горячей штамповки сертификата подлинности в общем случае зависит от количества доступных попыток. Здесь предложена методика для уменьшения количества вражеских попыток K T путем обнаружения аномального поведения волокон вокруг подписанных концевых точек волокна в ходе проверки.

Блоки издания и проверки сертификата подлинности повторяют свои части алгоритма А3 для каждого квадранта Si объекта аутентификации. Блок издания первоначально сканирует экземпляр объекта аутентификации и собирает информацию о множестве точек N, освещаемых, когда Si освещен. Затем, используя имеющиеся Λ битов, он сжимает наибольшее подмножество P⊂N, |P|=G, возвращенное А2. Затем А3 находит подмножество U⊂S-S i , такое, что эвклидово расстояние между каждой единицей u i ∈ U и ближайшей к ней единицей p j ∈P не превышает ε 1 . Подмножество U единиц представляет ε1-окрестность Р. Затем блок издания подсчитывает количество

K T точек в N, которые принадлежат U. Поскольку K T должно быть больше G, чтобы предотвратить ложные отрицательные результаты, блок издания сохраняет помимо Р разность ε2 = K T — G в сообщении m, которое позднее подписывается с использованием личного ключа блока издания (см. раздел II). Используя общий ключ блока издания, блок проверки извлекает из присоединенной подписи сжатое подмножество Р точек и

ε2 и воссоздает соответствующую ε1-окрестность U. Затем блок проверки сканирует экземпляр объекта аутентификации на предмет множества освещенных волокон N’, когда Si освещен. Он объявляет, что экземпляр подлинный, проверяя, что количество общих точек в U и N’ не больше G+ε2 и что количество общих точек в N’ и P не меньше Gζ.

Благодаря сохранению ε2 в подписи противнику приходится использовать не более K T = G + ε2 попыток позиционирования волокон в ε1-окрестности Р. Целью противника является размещение, по меньшей мере, концевых точек волокна из Р точно, следовательно, противник может позволить себе G(1 — ζ) + ε2 неправильных размещений, находящихся в ε1-окрестности Р в процессе горячей штамповки. Ожидается, что каждая попытка, нацеленная на точку p i, в случае неудачи заканчивается в ε1-окрестности p i. Увеличивая ε1, блок проверки может идентифицировать возможные неправильные размещения в более обширной окрестности; однако это также увеличивает ожидание для ε2-значения, которое разработчик сертификата подлинности желает сохранять как можно меньшим.

Ниже показана эмпирическая методология проектирования, которая принимает данное ε1=const, а затем добивается максимизации главной цели ζf(A2) с точки зрения нескольких параметров сертификата подлинности.

В. Проектирование системы СП

Задача 3. Цель проектирования для системы СП

Для данных алгоритма сжатия А2, фиксированного RK ≤ Φ, ζ, ε1 и Λ, среза * ,K * > имеющегося волокна, которое максимизирует:

где ζf является стоимостью горячей штамповки экземпляра СП.

На фиг.12 показано графическое представление конструкции сертификата подлинности для оптимизированных эффективностей стоимости. По оси абсцисс отложена длина R волокна относительно L, а по оси ординат показано количество волокон L. Полоска иллюстрирует логарифм стоимости горячей штамповки log10f(A2,R,K)) с лимитом ограничения Λ = 512 битов и набором фиксированных параметров: ζ =0.9, ε1 = 8 и v = 0.8. На чертеже также показано качество решений для всех срезов волокна фиксированной длины RK = Φ = 100L.

Можно использовать простую эмпирическую методику, которая ищет наилучший срез волокна * ,K * >. Процедура поиска показана на фиг.12. По оси абсцисс и ординат отложены значения R и K соответственно. Полоска обозначает ожидаемый логарифм стоимости горячей штамповки экземпляра сертификата подлинности, log10f(A2,R,K)). Стоимость дана в отношении R и K и для фиксированного набора параметров: Λ=512, ζ=0.9, ε1=8 и v=0.8. Диаграмма на фиг.12 вычислена эмпирически. А2 применяется к 500 произвольно сгенерированным экземплярам сертификата подлинности (512,R,K) с каждой комбинацией из R= и K=<80, 96, . 192, 256, 384, 512, 768 ,1024>. Ожидаемая производительность сжатия для каждой точки в оставшейся части пространства > получена интерполяцией эмпирических результатов. Согласно фиг.12, наилучший срез волокна можно получить в окрестности K * ≈ 900 и R * ≈ 0.1L. Этот результат говорит о том, что для выбранной среды проектирования крестообразный сертификат подлинности является наилучшей опцией. Заметим, что тщательный выбор среза волокна привел к повышению на порядок величины стоимости горячей штамповки в отношении произвольно выбранной точки на RK = Φ. Эмпирические принципы, используемые в этом примере, можно применить к поиску набора параметров, близких к оптимальным, для разных сред и производственных ограничений сертификата подлинности.

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

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

Компоненты вычислительного устройства 1300 могут включать в себя, но не только, процессор 1302 (например, любой из микропроцессоров, контроллеров и т.п.), системную память 1304, устройства 1306 ввода, устройства 1308 вывода и сетевые устройства 1310.

Вычислительное устройство 1300 обычно включает в себя разнообразные компьютерно-считываемые носители. Такие носители могут представлять собой любые имеющиеся носители, к которым может осуществлять доступ вычислительное устройство 1300, и включают в себя энергозависимые и энергонезависимые носители, сменные и стационарные носители. Системная память 1304 включает в себя компьютерно-считываемый носитель в виде оперативной памяти (ОЗУ) и/или энергонезависимой памяти, например постоянной памяти (ПЗУ). Базовая система ввода/вывода (BIOS), содержащая основные процедуры, которые помогают переносить информацию между элементами вычислительного устройства 1300, например, при запуске, хранится в системной памяти 1304. Системная память 1304 обычно содержит данные и/или программные модули, непосредственно доступные процессору 1302 и/или в данный момент обрабатываемые им.

Системная память 1304 также включает в себя другие сменные/стационарные, энергозависимые/энергонезависимые компьютерные носители информации. Например, это может быть жесткий диск для считывания со стационарного, энергонезависимого носителя и записи на него; это может быть привод магнитных дисков для считывания со сменного, энергонезависимого носителя (например, “флоппи-диска”) и записи на него; и привод оптических дисков для считывания со стационарного, энергонезависимого носителя и/или записи на него, например CD-ROM, DVD или другой тип оптического носителя.

Приводы и соответствующие компьютерно-считываемые носители обеспечивают энергонезависимое хранение компьютерно-считываемых команд, структур данных, программных модулей и других данных для вычислительного устройства 1300. Очевидно, что для реализации иллюстративного вычислительного устройства 1300 также можно использовать другие типы компьютерно-считываемых носителей, на которых могут храниться данные, к которым вычислительное устройство 1300 может осуществлять доступ, например магнитные кассеты или другие магнитные запоминающие устройства, карты флэш-памяти, CD-ROM, цифровые универсальные диски (DVD) или другие оптические запоминающие устройства, блоки оперативной памяти (ОЗУ), блоки постоянной памяти (ПЗУ), электрически стираемые программируемые постоянные запоминающие устройства (ЭСППЗУ) и т.п. В системной памяти 1304 может храниться любое количество программных модулей, например операционная система 1320, прикладные программы 1328 и данные 1332.

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

Пользователь может вводить команды и информацию в вычислительное устройство 1300 через устройства 1306 ввода, например клавиатуру и указательное устройство (например, “мышь”). Другие устройства 1306 ввода могут включать в себя микрофон, джойстик, игровую панель, контроллер, спутниковую антенну, последовательный порт, сканер, сенсорный экран, сенсорные панели, кнопочные панели и/или т.п. Устройства 1308 вывода могут включать в себя монитор на основе ЭЛТ, экран ЖКД, громкоговорители, принтеры и т.п.

Вычислительное устройство 1300 может включать в себя сетевые устройства 1310 для подключения к компьютерным сетям, например локальной сети (ЛС), глобальной сети (ГС) и т.п.

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

1. Способ кодирования произвольно распределенных признаков в объекте, содержащий этапы, на которых
определяют произвольно распределенные признаки в объекте,
определяют функцию плотности вероятности, связанную с объектом,
сжимают данные, представляющие произвольно распределенные признаки, при этом сжатие основано частично на функции плотности вероятности,
кодируют сжатые данные с помощью подписи, и
создают ярлык, содержащий объект и кодированные данные;
определяют векторы, связанные с произвольно распределенными признаками, основываясь, по меньшей мере, частично на функции плотности вероятности; и
кодируют векторы с использованием алгоритма арифметического кодирования, при этом алгоритм арифметического кодирования содержит:
Задать U как список всех единичных областей в S-Si-u.
Список всех помеченных единиц, М(u), задан как М(u)=⌀
делать
Найти все единичные области V=argminν⊂U ||Qν-Qu||
делать
Найти единичную область w=argmaxν∈V ξ(l,ν)
Задать диапазон АК для w равным γ(w,u) (см. уравнения 17, 18)
Множество узлов перед w равно Mw(u)=М(u)
M(u)=M(u)∪w, V=V-w, U=U-w.
пока V≠⌀
пока U≠⌀
при этом S означает зону сертификата подлинности объекта, Si означает конкретную область сертификата подлинности объекта, ξ(l,ν) означает вероятность того, что зона содержит освещенные концевые точки волокна, АК означает арифметический кодер, который преобразует входной поток произвольной длины в одно рациональное число в пределах [0,1>, u означает единичный квадрат, U означает единичные квадраты, Q означает главную точку единицы, v означает освещенную единицу относительно u, argmax означает правило приоритетов, установленное таким образом, что освещенная единица, которая имеет наибольшую вероятность освещения кодируется первой, М означает набор единиц, и γ(w,u) означает рабочий диапазон, используемый АК для кодирования w.

2. Способ по п.1, в котором при кодировании векторов с использованием алгоритма арифметического кодирования определяют путь для соединения части векторов в фиксированном объеме данных.

3. Способ по п.1, в котором произвольно распределенные признаки представляют собой волокна, произвольно размещенные в объекте.

4. Способ по п.3, в котором функция плотности вероятности представляет вероятность того, что волокна в конкретной области освещены источником света.

5. Способ по п.3, в котором функцию плотности вероятности выводят на основании, по меньшей мере, частично длины волокон.

6. Способ по п.3, в котором каждый вектор представляет концевые точки двух волокон.

7. Способ по п.1, в котором данные кодируют с помощью личного ключа.

8. Способ по п.1, в котором ярлык представляет собой сертификат подлинности, способный к самоаутентификации, и объект представляет собой объект аутентификации, входящий в состав сертификата подлинности.

9. Способ по п.1, в котором кодированные данные включают в ярлык в качестве штрих-кода.

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

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

12. Способ по п.10, в котором алгоритм представляет собой криптографический алгоритм SHA1.

13. Одно или несколько компьютерно-считываемых запоминающих устройств для хранения команд, выполняемых процессором для осуществления способа по п.1.

14. Система для кодирования произвольно распределенных признаков в объекте, содержащая
блок издания, сконфигурированный с возможностью определять произвольно распределенные признаки в объекте аутентификации и сжимать данные, представляющие произвольно распределенные признаки, содержащие волокна, при этом блок издания также сконфигурирован с возможностью кодирования сжатых данных с помощью подписи и создания ярлыка, содержащего объект аутентификации и кодированные данные,
при этом блок издания также сконфигурирован с возможностью определения функции плотности вероятности, связанной с объектом аутентификации, причем функция плотности вероятности определена как вероятность нахождения второго конца волокна в данном местоположении с неосвещенной областью, когда первый конец волокна расположен в освещенной области объекта аутентификации, определения векторов, связанных с произвольно распределенными признаками, основываясь, по меньшей мере, частично на функции плотности вероятности, и кодирования части векторов в виде пути с применением алгоритма арифметического кодирования, содержащего
Задать U как список всех единичных областей в S-Si-u.
Список всех помеченных единиц, М(u), задан как М(u)=⌀
делать
Найти все единичные области V=argminν⊂U ||Qν-Qu||
делать
Найти единичную область w=argmaxν∈V ξ(l,ν)
Задать диапазон АК для w равным γ(w,u) (см. уравнения 17, 18)
Множество узлов перед w равно Mw(u)=М(u)
M(u)=M(u)∪w, V=V-w, U=U-w.
пока V≠⌀
пока U≠⌀,
при этом S означает зону сертификата подлинности объекта, Si означает конкретную зону сертификата подлинности объекта, ξ(l,v) означает вероятность того, что зона содержит освещенные концевые точки волокон, АК означает арифметический кодер, который преобразует входной поток произвольной длины в единичное рациональное число в [0,1>, u означает единичный квадрат, U означает единичные квадраты, Q означает главную точку единицы, v означает освещенную единицу относительно u, argmax означает правило приоритетов, установленное таким образом, что освещенная единица, которая имеет наибольшую вероятность освещения, кодируется первой, М означает набор единиц и γ(w,u) означает рабочий диапазон, используемый АК для кодирования w.

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

16. Система по п.14, в которой блок издания также обеспечивает включение в ярлык штрих-кода с кодированными данными.

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

18. Система по п.17, в которой блок издания также обеспечивает шифрование сжатых данных с использованием хэшированных текстовых данных и включение текстовых данных в ярлык.

19. Система по п.14, дополнительно содержащая блок проверки, способный декодировать данные, представляющие произвольно распределенные признаки в ярлыке, и аутентифицировать ярлык путем сравнения декодированных данных с данными действительных произвольно распределенных признаков, определенных из объекта аутентификации.

20. Аутентификационный ярлык, содержащий
объект аутентификации, содержащий произвольно распределенные признаки, и
кодированную информацию, связанную с объектом аутентификации, причем информация закодирована с помощью подписи и содержит сжатые данные, представляющие произвольно распределенные признаки в объекте аутентификации, при этом данные в кодированной информации сжаты путем
определения функции плотности вероятности, связанной с объектом аутентификации,
определения векторов, связанных с произвольно распределенными атрибутами, на основании, по меньшей мере, частично функции плотности вероятности, и
кодирования векторов с использованием алгоритма арифметического кодирования,
при этом ярлык допускает самоаутентификацию путем сравнения сжатых данных в кодированной информации и данных, представляющих произвольно распределенные признаки, полученных путем анализа объекта аутентификации, при этом
сжатые данные получают путем:
определения векторов, связанных с произвольно распределенными признаками, основываясь, по меньшей мере, частично на функции плотности вероятности; и
кодирования векторов с применением алгоритма арифметического кодирования, содержащего
Задать U как список всех единичных областей в S-Si-u.
Список всех помеченных единиц, М(u), задан как М(u)=⌀
делать
Найти все единичные области V=argminν⊂U ||Qν-Qu||
делать
Найти единичную область w=argmaxν∈V ξ(l,ν)
Задать диапазон АК для w равным γ(w,u) (см. уравнения 17, 18)
Множество узлов перед w равно Mw(u)=М(u)
M(u)=M(u)∪w, V=V-w, U=U-w.
пока V≠⌀
пока U≠⌀,
при этом S означает зону сертификата подлинности объекта, Si означает конкретную зону сертификата подлинности объекта, ξ(l,ν) означает вероятность того, что зона содержит освещенные концевые точки волокон, АК означает арифметический кодер, который преобразует входной поток произвольной длины в единичное рациональное число в [0,1>, u означает единичный квадрат, U означает единичные квадраты, Q означает главную точку единицы, v означает освещенную единицу относительно u, argmax означает правило приоритетов, установленное таким образом, что освещенная единица, которая имеет наибольшую вероятность освещения, кодируется первой, М означает набор единиц и γ(w, u) означает рабочий диапазон, используемый АК кодирования w.

21. Ярлык по п.20, в котором кодированная информация включена в ярлык в качестве штрих-кода.

22. Ярлык по п.20, в котором кодированная информация закодирована с помощью личного ключа.

23. Ярлык по п.20, который также содержит текстовые данные, содержащие строку символов, причем сжатые данные зашифрованы с использованием текстовых данных.

24. Ярлык по п.23, в котором сжатые данные зашифрованы путем хэширования текстовых данных посредством алгоритма и шифрования сжатых данных с использованием хэшированных текстовых данных.

25. Устройство для создания ярлыка, содержащее
средство определения произвольно распределенных признаков в объекте аутентификации;
средство определения функции плотности вероятности, связанной с объектом аутентификации, при этом функция плотности вероятности определяет вероятность точки, содержащей освещенный второй конец волокна и обусловленной местоположением первого конца волокна в освещенной области;
средство сжатия данных, представляющих произвольно распределенные признаки, при этом сжатие основано частично на функции плотности вероятности;
средство кодирования сжатых данных с помощью подписи;
средство создания ярлыка, содержащего объект аутентификации и кодированные данные;
средство определения векторов, связанных с произвольно распределенными признаками, основываясь, по меньшей мере, частично на функции плотности вероятности; и
средство кодирования векторов с применением алгоритма арифметического кодирования, содержащего:
Задать U как список всех единичных областей в S-Si-u.
Список всех помеченных единиц, М(u), задан как М(u)=⌀
делать
Найти все единичные области V=argminν⊂U ||Qν-Qu||
делать
Найти единичную область w=argmaxν∈V ξ(l,ν)
Задать диапазон АК для w равным γ(w,u) (см. уравнения 17, 18
Множество узлов перед w равно Mw(u)=М(u)
M(u)=M(u)∪w, V=V-w, U=U-w.
пока V≠⌀
пока U≠⌀,
при этом S означает зону сертификата подлинности объекта, Si означает конкретную зону сертификата подлинности объекта, ξ(l,ν) означает вероятность того, что зона содержит освещенные концевые точки волокон, АК означает арифметический кодер, который преобразует входной поток произвольной длины в единичное рациональное число в [0,1>, u означает единичный квадрат, U означает единичные квадраты, Q означает главную точку единицы, v означает освещенную единицу относительно u, argmax означает правило приоритетов, установленное таким образом, что освещенная единица, которая имеет наибольшую вероятность освещения, кодируется первой, М означает набор единиц и γ(w, u) означает рабочий диапазон, используемый АК для кодирования w.

26. Устройство по п.25, дополнительно содержащее средство включения волокон в объект аутентификации в качестве произвольно распределенных признаков.

27. Устройство по п.25, дополнительно содержащее средство определения векторов, связанных с произвольно распределенными признаками, на основании, по меньшей мере, частично функции плотности вероятности и
средство кодирования векторов с использованием алгоритма арифметического кодирования.

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

29. Устройство по п.25, дополнительно содержащее средство аутентификации ярлыка путем сравнения кодированных данных с данными, связанными с произвольно распределенными признаками в объекте аутентификации.

Арифметическое кодирование

Сейчас существует множество алгоритмов сжатия информации. Большинство из них широко известны, но есть и некоторые весьма эффективные, но, тем не менее, малоизвестные алгоритмы. Эта статья рассказывает о методе арифметического кодирования, который является лучшим из энтропийных, но тем не менее мало кто о нём знает.
Прежде чем рассказывать об арифметическом кодировании, надо сказать пару слов об алгоритме Хаффмана. Этот метод эффективен, когда частоты появления символов пропорциональны 1/2 n (где n – натуральное положительное число). Это утверждение становится очевидным, если вспомнить, что коды Хаффмана для каждого символа всегда состоят из целого числа бит. Рассмотрим ситуацию, когда частота появление символа равна 0,2, тогда оптимальный код для кодирования это символа должен иметь длину –log2(0,2)=2,3 бита. Понятно, что префиксный код Хаффмана не может иметь такую длину, т.е. в конечном итоге это приводит к ухудшению сжатия данных.
Арифметическое кодирование предназначено для того, чтобы решить эту проблему. Основная идея заключается в том, чтобы присваивать коды не отдельным символам, а их последовательностям.
Вначале рассмотрим идею, лежащую в основе алгоритма, затем рассмотрим небольшой практический пример.
Как и во всех энтропийных алгоритмах мы обладаем информацией о частоте использования каждого символа алфавита. Эта информация является исходной для рассматриваемого метода. Теперь введём понятие рабочего отрезка. Рабочим называется полуинтервал [a;b) с расположенными на нём точками. Причём точки расположены т.о., что длины образованных ими отрезков равны частоте использования символов. При инициализации алгоритма a=0 b=1.
Один шаг кодирования заключается в простой операции: берётся кодируемый символ, для него ищется соответствующий участок на рабочем отрезке. Найденный участок становится новым рабочим отрезком (т.е. его тоже необходимо разбить с помощью точек).
Эта операция выполняется для некоторого количества символов исходного потока. Результатом кодирования цепочки символов является любое число (а также длина его битовой записи) с итогового рабочего отрезка (чаще всего берётся левая граница отрезка).
Звучит это довольно сложно. Давайте попробуем разобраться с помощью небольшого примера. Закодируем сообщение «ЭТОТ_МЕТОД_ЛУЧШЕ_ХАФФМАНА» с помощью описанного метода.

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

Берём первый символ из потока, это символ «Э». Соответствующий ему отрезок – отрезок [0,96;1). Если бы мы хотели закодировать один символ, то результатом кодирования было бы любое число из этого отрезка. Но мы не остановимся на одном символе, а добавим ещё один. Символ «Т». Для этого составим новый рабочий отрезок с a=0,96 и b=1. Разбиваем этот отрезок точками точно так же как мы сделали это для исходного отрезка и считываем новый символ «Т». Символу «Т» соответствует диапазон [0,24;0,36), но наш рабочий отрезок уже сократился до отрезка [0,96;1). Т.е. границы нам необходимо пересчитать. Сделать это можно с помощью двух следующих формул: High=Lowold+(Highold-Lowold)*RangeHigh(x), Low=Lowold+(Highold-Lowold)*RangeLow(x), где Lowold – нижняя граница интервала, Highold – верхняя граница интервала RangeHigh и RangeLow – верхняя и нижняя границы кодируемого символа.
Пользуясь этими формулами, закодируем первое слово сообщения целиком:

Результатом кодирования будет любое число из полуинтервала [0,97218816; 0,97223424).
Предположим, что результатом кодирования была выбрана левая граница полуинтервала, т.е. число 0,97218816.
Рассмотрим процесс декодирования. Код лежит в полуинтервале [0,96;1). Т.е. первый символ сообщения «Э». Чтобы декодировать второй символ (который кодировался в полуинтервале [0,96;1)) полуинтервал нужно нормализовать, т.е. привести к виду [0;1). Это делается с помощью следующей формулы: code=(code-RangeLow(x))/(RangeHigh(x)-RangeLow(x)), где code – текущее значение кода.
Применяя эту формулу, получаем новое значение code=(0,97218816-0,96)/(1-0,96)= 0,304704. Т.е. второй символ последовательности «Т».
Снова применим формулу: code=(0,304704-0,24)/(0,36-0,24)= 0,5392. Третий символ последовательности – «О».
Продолжая декодирование, по описанной схеме мы можем полностью восстановить исходный текст.

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

Кодирование целых и действительных чисел

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

Для кодирования целых чисел от 0 до 255 достаточно иметь 8 разрядов двоичного кода (8 бит). 16 бит позволяют закодировать целые числа от 0 до 65 535, а 24 бит — уже более 16,5 млн разных значений.

Для кодирования действительных чисел используют 80-раз- рядное кодирование. При этом число предварительно преобразуется в нормализованную форму:

Первая часть числа называется мантиссой, а вторая — характеристикой. Большую часть из 80 бит отводят для хранения мантиссы (вместе со знаком), и некоторое фиксированное количество разрядов отводят для хранения характеристики (тоже со знаком).

НАУЧНАЯ БИБЛИОТЕКА — РЕФЕРАТЫ — Арифметическое кодирование. Кодирование длин повторений

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Реферат на тему:

«Арифметическое кодирование. Кодирование длин повторений»

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

Поясним идею арифметического кодирования на простейшем примере. Пусть нам нужно закодировать следующую текстовую строку: РАДИОВИЗИР.

Пеpед началом pаботы кодера соответствующий кодируемому тексту исходный интеpвал составляет [0; 1).

Алфавит кодируемого сообщения содержит следующие символы (буквы): < Р, А, Д, И, О, В, З >.

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

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

Итак, перед началом кодирования исходный интервал составляет [0 — 1).

После пpосмотpа пеpвого символа сообщения Р кодер сужает исходный интеpвал до нового — [0.8; 1), котоpый модель выделяет этому символу. Таким образом, после кодирования первой буквы результат кодирования будет находиться в интервале чисел [ 0.8 — 1).

Следующим символом сообщения, поступающим в кодер, будет буква А. Если бы эта буква была первой в кодируемом сообщении, ей был бы отведен интервал [ 0 — 0.1 ), но она следует за Р и поэтому кодируется новым подынтервалом внутри уже выделенного для первой буквы, сужая его до величины [ 0.80 — 0.82 ). Другими словами, интервал [ 0 — 0.1 ), выделенный для буквы А, располагается теперь внутри интервала, занимаемого предыдущим символом (начало и конец нового интервала определяются путем прибавления к началу предыдущего интервала произведения ширины предыдущего интервала на значения интервала, отведенные текущему символу). В pезультате получим новый pабочий интеpвал [0.80 — 0.82), т.к. пpедыдущий интеpвал имел шиpину в 0.2 единицы и одна десятая от него есть 0.02.

Следующему символу Д соответствует выделенный интервал [0.1 — 0.2), что пpименительно к уже имеющемуся рабочему интервалу [0.80 — 0.82) сужает его до величины [0.802 — 0.804).

Следующим символом, поступающим на вход кодера, будет буква И с выделенным для нее фиксированным интервалом [ 0,3 — 0,6). Применительно к уже имеющемуся рабочему интервалу получим [ 0,8026 — 0,8032 ).

Пpодолжая в том же духе, имеем:

после пpосмотpа Р [0.8 — 1.0)

И [0.803034934 — 0.803034988)

Р [0.8030349772 — 0.8030349880)

Результат кодирования: интервал [0,8030349772 — 0,8030349880]. На самом деле, для однозначного декодирования теперь достаточно знать только одну границу интервала — нижнюю или верхнюю, то есть результатом кодирования может служить начало конечного интервала — 0,8030349772. Если быть еще более точным, то любое число, заключенное внутри этого интервала, однозначно декодируется в исходное сообщение. К примеру, это можно проверить с числом 0,80303498, удовлетворяющим этим условиям. При этом последнее число имеет меньшее число десятичных разрядов, чем числа, соответствующие нижней и верхней границам интервала, и, следовательно может быть представлено меньшим числом двоичных разрядов.

Нетрудно убедиться в том, что, чем шире конечный интервал, тем мен ь шим числом десятичных (и, следовательно, двоичных) разрядов он может быть представлен. Ширина же интервала зависит от распределения вероятностей кодиру е мых символов — более вероятные символы сужают интервал в меньшей степени и , следовательно, добавляют к результату кодирования меньше бит. Покажем это на простом примере.

Допустим, нам нужно закодировать следующую строку символов: A A A A A A A A A #, где вероятность буквы А составляет 0,9. Процедура кодирования этой строки и получаемый результат будут выглядеть в этом случае следующим образом:

Входной символ Нижняя граница Верхняя граница

Результатом кодирования теперь может быть, к примеру, число 0.35 , целиком попадающее внутрь конечного интервала 0.3486784401 — 0.387420489. Для двоичного представления этого числа нам понадобится 7 бит (два десятичных разряда соответствуют примерно семи двоичным ), тогда как для двоичного представления результатов кодирования из предыдущего примера — 0,80303498 — нужно 27 бит .

Декодирование

Пpедположим, что все что декодер знает о тексте, — это конечный интеpвал [0,8030349772 — 0,8030349880]. Декодеру, как и кодеру, известна также таблица распределения выделенных алфавиту интервалов. Он сpазу же понимает, что пеpвый закодиpованный символ есть Р, так как результат кодирования целиком лежит в интеpвале [0.8 — 1), выделенном моделью символу Р согласно таблице .

Тепеpь повтоpим действия кодера:

после пpосмотpа [0.8 — 1.0).

Исключим из результата кодирования влияние теперь уже известного первого символа Р, для этого вычтем из результата кодирования нижнюю границу диапазона, отведенного для Р, — 0,8030349772 — 0.8 = =0,0030349772 — и разделим полученный результат на ширину интервала, отведенного для Р, — 0.2. В результате получим 0,0030349772 / 0,2 = =0,015174886. Это число целиком вмещается в интервал, отведенный для буквы А, — [0 — 0,1) , следовательно, вторым символом декодированной последовательности будет А.

Поскольку теперь мы знаем уже две декодированные буквы — РА, исключим из итогового интервала влияние буквы А. Для этого вычтем из остатка 0,015174886 нижнюю границу для буквы А 0,015174886 — 0.0 = =0,015174886 и разделим результат на ширину интервала, отведенного для буквы А, то есть на 0,1. В результате получим 0,015174886/0,1=0,15174886. Результат лежит в диапазоне, отведенном для буквы Д, следовательно, очередная буква будет Д.

Исключим из результата кодирования влияние буквы Д. Получим (0,15174886 — 0,1)/0,1 = 0,5174886. Результат попадает в интервал, отведенный для буквы И, следовательно, очередной декодированный символ — И, и так далее, пока не декодируем все символы:

Декодируемое Символ Границы Ширина

число на выходе нижняя верхняя интервала

0,8030349772 Р 0.8 1.0 0.2

0,015174886 А 0.0 0.1 0.1

0.0 Конец декодирования

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

Первая состоит в том, что декодеру нужно обязательно каким-либо образом дать знать об окончании процедуры декодирования, поскольку остаток 0,0 может означать букву а или последовательность аа, ааа, аааа и т.д. Решить эту проблему можно двумя способами.

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

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

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

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

Кодирование длин повторений

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

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

Предположим, что нужно закодировать двоичное (двухцветное) изображение размером 8 х 8 элементов, приведенное на рис. 1.

Просканируем это изображение по строкам (двум цветам на изображении будут соответствовать 0 и 1), в результате получим двоичный вектор данных

длиной 64 бита (скорость исходного кода составляет 1 бит на элемент изображения).

Выделим в векторе X участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков — положительных целых чисел, соответствующих исходному вектору данных X, — будет иметь вид r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4).

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

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL