Скачати 195.42 Kb.
|
МЕТОД СЖАТИЯ ДВОИЧНЫХ СООБЩЕНИЙ НА ОСНОВЕ МНОГОЗНАЧНЫХ БИНОМИАЛЬНЫХ ЧИСЕЛ И УСТРОЙСТВО ДЛЯ ЕГО РЕАЛИЗАЦИИ Т.А. Протасова, ст. преп. Сумский государственный университет Под сжатием информации понимают операцию, в результате которой данному коду или сообщению ставится в соответствие более короткий код или сообщение [1]. Актуальность проблемы сжатия различных сигналов в настоящее время очевидна. Особенно важно сжимать изображения. Простые расчеты показывают, что сжатие изображений является фактически обязательным для уменьшения требований к емкости массовой памяти и скоростям передачи для систем, связанных с хранением и обработкой неподвижных и видеоизображений. Для цифрового представления 35-мм негатива, сканированного с разрешением 12мкм, требуется около 144 Мбит (2048*3072 ЭИ при24 бит/ЭИ). Цифры становятся еще более впечатляющими, если говорить об истинных видеофильмах с движущимися изображениями. Для хранения одной секунды несжатого цветного видеофильма при скорости 30 кадров в секунду требуется 512*480 ЭИ/кадр при 24 бит/ЭИ, или 180 Мбит. Следует отметить, что методы и устройства сжатия различных сигналов (в том числе и телевизионных) интенсивно развивались с 70-х годов, но только в последнее время на базе новых электронных технологий достигнуты значительные результаты. Достаточно эффективным оказалось нумерационное кодирование данных [ 2 ]. Для сжатия и восстановления изображений можно использовать как преимущественно аппаратные средства, так и программный способ реализации алгоритма. Выбор способа определяется тремя основными факторами: размером изображения, скоростью передачи данных и сложностью алгоритма. Программный способ реализации предпочтителен, как правило, для алгоритмов сжатия и восстановления небольших неподвижных изображений, особенно если скорость не имеет первостепенного значения. Программные средства можно использовать также для реализации алгоритмов восстановления движущихся изображений, поскольку эти алгоритмы требуют менее интенсивных вычислений, чем алгоритмы сжатия данных. Системы, осуществляющие сжатие / восстановление изображений аппаратными средствами, сейчас почти в 30 раз превосходят по быстродействию аналогичные программные системы с применением самых высокоскоростных компьютеров [ 3 ]. В данной работе к рассмотрению предлагается аппаратная реализация алгоритма сжатия нумерацией двоичных последовательностей на основе многозначной биномиальной системы счисления. Известные методы нумерации [ 2 ] осуществляют процедуру сжатия в течение одной процедуры. Однако эти методы сложны и трудно реализуемы аппаратно и при этом недостаточно универсальны. Устранить эти недостатки можно путем использования структурных систем счисления, в частности, многозначной биномиальной системы счисления [ 4 ]. При использовании структурных систем счисления нумерация осуществляется в два этапа: сначала организовывается переход к числу в биномиальной системе счисления, а затем происходит переход от этого числа к его номеру. Используемая в рассмотренном методе сжатия специальная система счисления с неоднородной структурой - многозначная q-ичная [ 4 ] биномиальная система счисления - характеризуется тем, что: а) ее диапазон и весовые значения разрядов задаются биномиальными коэффициентами; б) максимальное число разрядов в биномиальных числах равно k; в) количество r информационных разрядов для различных биномиальных чисел является переменным; г) алфавит используемых цифр с учетом нуля содержит m-k цифр, где m-параметр системы счисления, влияющий на ее диапазон; д) вес разряда зависит от его местоположения в числе, стоящей в нем цифры и предшествующих цифр; е) содержит контрольное число q=m-k, превышение которого в биномиальном числе приводит к появлению в нем ошибки. Числовая функция, представляющая многозначную биномиальную систему счисления, имеет следующий вид: ![]() где ![]() ![]() ![]() ![]() при следующих ограничениях: ![]() ![]() p-kі0 Если q - контрольное число, то q = n-p. При решении задачи нумерации сигналов двоичные последовательности рассматриваются как равновесные кодовые комбинации. Это объясняется тем, что подвергать процедуре сжатия путем нумерации можно только кодовые комбинации, характеризующиеся одинаковой вероятностью их генерирования. А равновесные кодовые комбинации как раз и характеризуются одинаковым количеством единиц и, как следствие, одинаковой вероятностью генерирования двоичных слов. Это свойство позволяет отнести равновесные коды к комбинаторным конфигурациям, которые наиболее удобно нумеровать с помощью биномиальных систем счисления. Задача нумерации равновесных кодов разбивается на два этапа и решается следующим образом: вначале осуществляется переход от двоичного кодового слова с постоянным весом к сочетанию, а затем к биномиальному многозначному слову и, наконец, в соответствии с выражением ( 1 ) - к степенной системе счисления, т.е. к номеру. Рассмотрим преобразования более подробно. Исходное двоичное слово характеризуется следующими параметрами: длиной слова - m и количеством единиц - k. Эти параметры являются исходными для определения параметра многозначной биномиальной системы счисления, который определяется согласно соотношению q=m-k. На следующем этапе формируют комбинаторную конфигурацию типа сочетания, затем осуществляется переход к биномиальному числу, далее производится подсчет количественного эквивалента биномиального числа. Данный алгоритм может быть представлен с помощью укрупненной блок-схемы, приведенной на рисунке 1. Рассмотрим более подробно каждую операцию данного преобразования. Подсчет количества единиц в кодовых комбинациях может быть реализован согласно блок-схеме алгоритма, приведенной на рисунке 2. При этом последовательно перебираются разряды заданного двоичного числа, начиная с нулевого, и в случае равенства единице анализируемого разряда устройство, фиксирующее количество единиц, должно увеличить на единицу свое состояние. Процесс прекращается, когда проанализирован последний (m-1)-й разряд двоичного числа. На следующем этапе определяется параметр биномиальной системы счисления, определяемый из соотношения q=m-k. Значения m и k чаще всего определяются характеристиками исходной двоичной кодовой комбинации. Обычно в качестве значения m фигурирует исходная длина двоичной кодовой комбинации. Длина комбинации определяется с помощью управляемого регистра. Значение k – количество единиц - подсчитывается. Далее определяется их разность. Чаще всего параметр многозначной биномиальной системы счисления задается заказчиком. Это обусловлено тем, что от значения параметра зависит диапазон переводимых чисел и, как следствие, характеристика помехоустойчивости получаемого кода.
При последующем преобразовании равновесного кодового слова необходимо последовательно в порядке возрастания записать адреса (номера разрядов) единиц в кодовых комбинациях. Полученная запись представляет собой комбинаторную конфигурацию типа сочетание. Например, равновесному кодовому слову 001100101 соответствует “сочетание” 1367. Это преобразование может быть реализовано с помощью блок-схемы алгоритма, приведенной на рисунке 3. Преобразование начинается с младшего разряда, которому при формировании сочетаний присваивается единичный номер, так как сформированная в результате преобразований конфигурация типа сочетания не может содержать нуль. Анализируется младший разряд. Если он равен единице, то адрес этого разряда записывается, иначе – теряется. Переход от сочетания к многозначному биномиальному числу организуем с помощью алгоритма, построенного на основе утверждения [ 5 ]. Утверждение. Если 1b2...bi...bк есть сочетание и если от каждой, кроме первой, bi цифры сочетания отнять предыдущую при счете слева направо цифру сочетания и единицу, а первая цифра равна старшей цифре сочетания, то полученная цифра ai= bi - bi-1 -1 является элементом последовательности, которая образует многозначное биномиальное число a1a2...ai...aк. ![]() ^ Алгоритм преобразования сочетания в многозначное биномиальное число имеет следующий вид. 1 Старшая цифра многозначного биномиального числа равна первой цифре сочетания. 2 Вычисляется следующая цифра многозначного биномиального числа ai= bi - bi-1 -1. 3 Пункт 2 повторять, пока не будет получена младшая цифра многозначного биномиального числа. Предложенный алгоритм реализуем с помощью блок-схемы, которая имеет вид, представленный на рисунке 4. Рассмотрим пример получения биномиального многозначного числа из сочетания. Пример. Преобразовать сочетание 1367 в многозначное биномиальное число. a1= b1 =1. a2= b2 - b1 -1 =3-1-1=1. a3= b3 - b3 -1 =6-3-1=2. a4= b4 - b3 -1 =7-6-1=0. Получено многозначное биномиальное число 1120. Переход от многозначного биномиального числа к номеру может быть осуществлен путем подстановки в ( 1 ) вместо Xi их значений и вычисления количественного эквивалента биномиального числа в десятичной системе счисления. Рассмотрим пример вычисления количественного эквивалента полученного биномиального числа. ![]() ^ Зададимся исходными значениями. Так как k=4, q=m-k=5,то X3=1, ![]() X2=1, ![]() X1=2, ![]() X0=0, ![]() Десятичный эквивалент биномиального числа 1120 равен ![]() При получении номера биномиального многозначного числа используется принцип поразрядного взвешивания. Разряды, представленные в биномиальном числе значениями, отличными от нуля, будут присутствовать в номере в качестве их десятичного эквивалента, а те разряды, которые раны нулю, – нет. Необходимо отметить, что анализ приведенных блок – схем алгоритмов позволил сделать вывод о том, что алгоритмы под номерами 2 и 3 практически идентичны, за исключением одной операции. Это говорит о том, что при последовательном вводе двоичного числа, которое должно преобразовываться, можно практически одновременно выполнять операцию подсчета количества единиц в кодовой комбинации и операцию формирования комбинаторной конфигурации – сочетания по записи адресов тех же единиц. Разработанные алгоритмы необходимо представить в виде устройства, реализовывающего рассмотренные функции. Структурная схема нумератора двоичных последовательностей на основе многозначных биномиальных чисел может иметь вид, представленный на рисунке 6. ![]() ^ Схема должна содержать следующие основные узлы: - счетчик длины слова и счетчик количества единиц; - регистр исходного двоичного числа; - формирователь многозначных биномиальных чисел; - схему сравнения; - формирователь ![]() - накопитель номера. Управлять работой устройства и синхронизировать ее должна схема управления. Так как при решении задачи нумерации двоичных слов на основе биномиальной системы счисления с многозначным алфавитом выделяется два этапа – вначале осуществляется переход от двоичного слова с постоянным весом к биномиальному многозначному слову, а затем осуществляется нумерация полученной многозначной биномиальной комбинации, то соответственно целесообразно устройство организовать таким образом, чтобы функционально можно было выделить узлы, решающие соответственно первую и вторую задачи. Это разделение функций возложим на управляющий триггер. В начальный момент работы устройства с приходом импульса «сброс» все элементы памяти установим в начальное состояние. Удобно отталкиваться от начальных значений, записанных в триггерах, счетчиках и регистрах, равных нулю. Запоминающие устройства, которые должны начинать работать с других исходных значений, будут установлены в них специальными сигналами. ![]() ^ Таким образом, управляющий триггер находится в нулевом состоянии. В следующий момент на вход установки триггера в единичное состояние подается сигнал «пуск», представляющий собой короткий импульс положительной полярности для установки триггера в режим работы «формирование биномиальной кодовой комбинации». Таким образом, на прямом выходе триггера управления формируется уровень логической единицы. К управляющим сигналам «сброс» и «пуск» предъявляются следующие требования:
Логическая единица с прямого выхода управляющего триггера разрешает прохождение импульсов от генератора на схему формирования биномиального многозначного числа. Эта часть схемы содержит входной параллельно-последовательный регистр, в который при включении в параллельном коде заносится исходная двоичная кодовая комбинация. В следующем такте осуществляется преобразование параллельного кода в последовательный. Двоичная кодовая комбинация последовательно появляется на выходе регистра, к которому подключена схема совпадения, на второй вход которой поступают управляющие импульсы. Выход схемы совпадения подключается к суммирующему входу счетчика единиц. Если соответствующий бит двоичного слова равен единице, то на выходе схемы совпадения появляется уровень логической единицы и импульс от генератора проходит на счетчик единиц. Состояние счетчика, таким образом, увеличивается на единицу. Если же разряд двоичного слова равен нулю, то схема совпадения запрещает прохождение импульса от генератора и состояние счетчика не меняется. Таким образом, производится подсчет количества единиц в принятой кодовой комбинации. Одновременно осуществляется формирование сочетаний по адресам единиц. Рассмотрим подробно эту процедуру. Схема формирования сочетаний содержит дешифратор, подсоединенный к выходу счетчика единиц, регистр сочетаний, содержащий регистры, количество которых определяется максимально возможным числом единиц в нумеруемой кодовой комбинации, и счетчик адресов. Счетчик адресов переключается синхронно с устройством, организующим сдвиг двоичной комбинации. В первый момент времени содержимое счетчика адресов должно быть на единицу больше содержимого счетчика единиц. В начальный момент времени счетчик единиц находится в нулевом состоянии, соответственно на вход дешифратора поступает нулевая кодовая комбинация, которая активизирует нулевой выход дешифратора. Логическая единица с выхода дешифратора выбирает первый регистр регистра сочетаний. Счетчик адресов находится в единичном состоянии, и с его выхода это значение подается на входы данных первого регистра. Если первый бит нумеруемой двоичной кодовой комбинации равен единице, то в первый разряд сочетания с выхода счетчика адресов запишется в двоичном коде его содержимое. По следующему управляющему сигналу счетчик единиц и счетчик адресов поменяют свое состояние. Происходит переход к анализу следующего разряда двоичной кодовой комбинации. При этом счетчик единиц находится в единичном состоянии, активизирует первый выход дешифратора, подключая второй регистр регистра сочетаний. В счетчике адресов записана в двоичном коде двойка. Предположим, что следующий разряд равен нулю. Этот нулевой сигнал с последовательного выхода регистра двоичного числа запрещает прохождение импульса от генератора на суммирующий вход счетчиков единиц. Счетчик единиц не меняет своего состояния. Соответственно в следующем такте по-прежнему будет активизирован первый выход дешифратора, и соответственно для записи будет по-прежнему подключен второй регистр сочетаний. Счетчик адресов меняет свое состояние, так как он перебирает адреса всех разрядов двоичного числа, а не только единичных. При анализе следующего бита двоичной кодовой комбинации процедура повторяется. Счетчик единиц находится в единичном 143состоянии, код, соответствующий единице, поступает на вход дешифратора и активизирует его первый выход. В счетчике адресов записана тройка. Если третий бит двоичной кодовой комбинации – единица, по сигналу разрешения содержимое счетчика адресов запишется во второй регистр сочетаний. Счетчик единиц увеличит свое содержимое на единицу. Если же и этот разряд окажется равным нулю, то содержимое счетчика единиц не изменится, по-прежнему будет активизирован первый выход дешифратора, который подключает второй регистр сочетаний. Счетчик адресов поменяет свое состояние. Описанная процедура будет повторяться до тех пор, пока не будет проанализирована вся исходная кодовая комбинация. При сдвиге двоичного числа целесообразно подавать на его последовательный вход D сигнал логического нуля. Когда будет сдвинут последний бит исходного числа в регистре, таким образом, окажутся записанными во всех разрядах нули. При этом в регистре сочетаний будет сформирована комбинаторная конфигурация – сочетание – номера адресов единичных разрядов двоичного числа. В следующем такте необходимо перейти от сочетания к многозначному биномиальному числу. Это преобразование осуществляется для каждого разряда отниманием от старшего значения сочетания значения разряда, младшего по отношению к нему. Эта процедура не выполняется только для самого старшего разряда сочетания. Старший разряд биномиального числа будет равен, таким образом, старшему разряду сочетания. Эту функцию удобно организовать на основе двоичных сумматоров, выполняя суммирование в дополнительном коде. Результат суммирования необходимо записать для хранения в регистр биномиального числа. Таким образом, получено многозначное биномиальное число, которое соответствует исходному двоичному. Сигнал разрешения записи результата суммирования в регистр многозначного биномиального числа при равенстве всех разрядов входного регистра нулю можно считать разрешением нумерации полученного биномиального числа. Этот сигнал поступает на вход сброса управляющего триггера и переводит его в нулевое состояние. Нулевой сигнал с прямого выхода триггера запрещает прохождение импульсов от генератора на схему формирования биномиального числа. Единичный сигнал с инверсного выхода управляющего триггера подается на схему совпадения, подключенную к инверсному выходу управляющего триггера, разрешая тем самым прохождение управляющих импульсов на схему нумерации биномиального числа. Для подсчета количественного эквивалента (номера) многозначного биномиального числа используется выражение кодообразующей функции (1) числа в биномиальной системе счисления с многозначным алфавитом [4]. Эта формула построена по принципу аддитивности, т.е. производит суммирование количественных эквивалентов каждого разряда числа. Например, для биномиального числа 3102 и параметров m=10 и k=4 подсчет количественного эквивалента будет производиться согласно следующей сумме: ![]() Это соответствует записи числа в более общей форме: ![]() Каждая сумма ![]() ![]() ![]() ![]() Схема узла нумерации биномиальных чисел должна содержать следующие основные узлы:
В качестве счетчика единиц целесообразно использовать счетчик единиц, который присутствует в схеме формирования биномиального числа, тем более что по окончанию процесса формирования биномиального числа в счетчике единиц записано необходимое в дальнейшем для нумерации значение количества единиц. При нумерации биномиального числа этот счетчик должен работать в обратном направлении, то есть уменьшать свое состояние. Поэтому в качестве счетчика единиц удобно выбрать реверсивный счетчик, который в режиме формирования биномиального числа будет суммировать, а в режиме нумерации – вычитать. Исходное многозначное биномиальное число необходимо записать в регистр для удобства обращения к данным, предназначенным для длительного хранения. Устройство формирования биномиального числа уже имеет такой регистр, предназначенный для хранения данных. При выполнении нумерации биномиального числа удобнее оперировать данными, записанными в счетчик. В процессе нумерации количество тактов суммирования определяется значениями разрядов биномиального числа, при чем по каждому такту суммирования значение разряда должно уменьшаться на единицу. Очевидно, что данную функцию целесообразно возложить на вычитающий счетчик, в который вначале преобразования запишется исходное биномиальное число. Так как длина биномиального числа определяется параметром k, а каждый разряд биномиального числа не может превышать значения q=m-k, то источник биномиального числа будет представлять собой параллельное соединение k счетчиков, каждый из которых состоит не менее чем из ![]() На инверсном выходе триггера формируется сигнал «логической единицы», который подается на один из входов схемы совпадения, на второй вход которой поступают импульсы от генератора. Сигналы с выхода элемента совпадения являются тактируемыми для разрабатываемого устройства. В дальнейшем будем называть эти сигналы просто «такт». Рассмотрим работу схемы по тактам. Такт 1 В счетчике-источнике многозначного биномиального числа записано число, которое необходимо преобразовать в номер. В счетчиках параметров записаны значения (m-1) и (k-1), которые поступают на входы схемы – формирователя числа сочетаний. Формирователь выдает значение ![]() В начале работы устройства в счетчиках биномиального числа поразрядно записано представление многозначного биномиального числа в двоичном коде. Количественный эквивалент биномиального числа зависит от количества его разрядов и значения каждого разряда числа, так как в основе формирования биномиального числа лежит принцип поразрядного взвешивания. От значения разрядов зависит количество тактов преобразования и формируемые формирователем сочетаний значения числа сочетаний. Значение ![]() Процесс преобразования, таким образом, завершен, и в регистре накопителя будет записан номер многозначного биномиального числа (его количественный эквивалент), для двоичного представления которого требуется меньше разрядов, чем для исходной комбинации. Таким образом, данный алгоритм и устройство, его реализующее, позволяют более эффективно сжимать информацию. В перспективе данный метод сжатия может быть применен для сжатия телевизионных изображений в процессе их обработки. SUMMARY The new compression method based on enumerating binary sequences by a binomial number system with a multiciphered alphabet is considered in the paper. The developed algorithms are described by examples. The structures of the compression algorithms and devices are given. ^
Поступила в редакцию 5 декабря 2003 г. |
![]() | Смкэс-2004 Известны системы ограничений для двоичных биномиальных чисел, полученные на основе структурного подхода. Данные системы ограничений... | ![]() | Смкэс-2004 удк 681. 37 Новый метод сжатия на основе биномиальной системы с многозначным алфавитом протасова Т. А., Бражник И. Е., Сумский государственный университет В работе предлагается новый метод сжатия изображений, основанный на нумерации биномиальных кодов |
![]() | Методы сжатия и защиты информации на основе биномиальных кодов борисенко А. А., д т. н., проф. Сумский государственный университет е-mail electron@sumdu edu ua Диапазон этих систем счисления также представляет биномиальный коэффициент. Известно, что множество всех двоичных чисел длины n можно... | ![]() | Сжатие двоичных кодов на основе биномиальных чисел Для сжатия равновесных кодов ранее были предложены простые алгоритмы, которые несложно реализовать аппаратными средствами. При этом... |
![]() | Средняя длина двоичных биномиальных чисел произвольного диапазона кулик И. А., к т. н доц. Сумский государственный университет И если задача вычисления средней длины указанных чисел для полного диапазона биномиальной системы счисления с параметрами и автором... | ![]() | Удк 621 037. 37 О средней длине двоичных биномиальных чисел Таким образом, целью данной работы является дальнейшее исследование линейных неравномерных биномиальных чисел. При этом решаемые... |
![]() | Удк 681. 518 Алгоритмы нумерации двоичных чисел с помощью биномиального счёта Они способны дать больший коэффициент сжатия информации, позволяющий в процессе сжатия находить ошибки используя для этого ключи,... | ![]() | Свойство вложенности двоичных биномиальных систем счисления и. А. Кулик, канд техн наук, доц С точки зрения практики это позволит, например, разработать адаптивные алгоритмы передачи данных на основе биномиальных кодов |
![]() | Формирование кодов-композиций на основе многозначных биномиальных чисел Второй, не менее важной проблемой, является проблема достоверности информации, так как появление ошибок может привести к тяжелым... | ![]() | Сложение двоичных чисел Таблица сложения двоичных чисел Сложение выполняем поразрядно, начиная с младшей цифры. Если получается больше 1, то записывается 0 и 1 добавляется к старшему разряду... |