Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп icon

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




Скачати 195.42 Kb.
НазваМетод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп
Дата14.07.2012
Розмір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, превышение которого в бино­миальном числе приводит к появлению в нем ошибки.

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


( 1 )


где , , ,

-цифра (r-j)-го разряда, j=1,2,...,r.

при следующих ограничениях:




`

p-kі0

Если q - контрольное число, то q = n-p.

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

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

Рассмотрим преобразования более подробно.

Исходное двоичное слово характеризуется следующими параметрами: длиной слова - m и количеством единиц - k. Эти параметры являются исходны­ми для определения параметра многозначной биномиальной системы счисле­ния, который определяется согласно соотношению q=m-k.

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

Данный алгоритм может быть представлен с помощью укрупненной блок-схемы, приведенной на рисунке 1.

Рассмотрим более подробно каждую операцию данного преобразования.

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

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

На следующем этапе определяется параметр биномиальной системы счисления, определяемый из соотношения q=m-k. Значения m и k чаще всего определяются характеристиками исходной двоичной кодовой комбинации.

Обычно в качестве значения m фигурирует исходная длина двоичной кодовой комбинации. Длина комбинации определяется с помощью управляемого регистра. Значение k – количество единиц - подсчитывается. Далее определяется их разность. Чаще всего параметр многозначной биномиальной системы счисления задается заказчиком. Это обусловлено тем, что от значения параметра зависит диапазон переводимых чисел и, как следствие, характеристика помехоустойчивости получаемого кода.





^ Рисунок 1 – Укрупненная блок-схема алгоритма функционирования






Рисунок 2 – Блок – схема алгоритма подсчета количества единиц в равновесной кодовой комбинации




При последующем преобразовании равновесного кодового слова необходимо последо­вательно в порядке возрастания записать адреса (номера разря­дов) единиц в ко­довых комбинациях. Полученная запись представляет со­бой комбинаторную конфигурацию типа сочетание. Например, равновесному кодовому слову 001100101 соответствует “сочетание” 1367. Это преобразование может быть реализовано с помощью блок-схемы алгоритма, приведенной на рисунке 3.

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

Переход от сочетания к многозначному биномиальному числу организу­ем с помощью алгоритма, построенного на основе утверждения [ 5 ].

Утверждение. Если 1b2...bi...bк есть сочетание и если от каж­дой, кроме первой, bi цифры сочетания отнять предыдущую при счете слева направо цифру сочетания и единицу, а первая цифра равна стар­шей цифре сочетания, то полученная цифра ai= bi - bi-1 -1 является элементом последовательности, кото­рая образует многозначное биноми­альное число a1a2...ai...aк.





^ Рисунок 3 – Блок-схема алгоритма получения сочетания


Алгоритм преобразования сочетания в многозначное биномиаль­ное число имеет следующий вид.

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 их значений и вы­числения количественного эквивалента биномиального числа в десятич­ной системе счис­ления. Рассмотрим пример вычисления количественного эквивалента полученного биномиального числа.





^ Рисунок 4 – Блок – схема алгоритма получения биномиального числа из сочетания


Зададимся исходными значениями.

Так как k=4, q=m-k=5,то

X3=1, ;

X2=1, ;

X1=2, ;

X0=0, .

Десятичный эквивалент биномиального числа 1120 равен = 56+15+7+0 = 78. Это число является номером равновесно­го кодового слова 011001010. Данный алгоритм можно реализовать с помощью блок – схемы, представленной на рисунке 5.

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

Необходимо отметить, что анализ приведенных блок – схем алгоритмов позволил сделать вывод о том, что алгоритмы под номерами 2 и 3 практически идентичны, за исклю­чением одной операции. Это говорит о том, что при последовательном вводе двоичного числа, которое должно преобразовываться, можно практически од­новременно выполнять операцию подсчета количества единиц в кодовой ком­бинации и операцию формирования комбинаторной конфигурации – сочетания по записи адресов тех же единиц.

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





^ Рисунок 5 – Блок – схема алгоритма получения количественного экви­валента многозначного биномиального числа

Схема должна содержать следующие основные узлы:

- счетчик длины слова и счетчик количества единиц;

- регистр исходного двоичного числа;

- формирователь многозначных биномиальных чисел;

- схему сравнения;

- формирователь ;

- накопитель номера.

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

Так как при решении задачи нумерации двоичных слов на основе биномиальной системы счисления с многозначным алфавитом выделяется два этапа – вначале осуществляется переход от двоичного слова с постоянным весом к биномиальному многозначному слову, а затем осуществляется нумерация полученной многозначной биномиальной комбинации, то соответственно целесообразно устройство организовать таким образом, чтобы функционально можно было выделить узлы, решающие соответственно первую и вторую задачи. Это разделение функций возложим на управляющий триггер. В начальный момент работы устройства с приходом импульса «сброс» все элементы памяти установим в начальное состояние. Удобно отталкиваться от начальных значений, записанных в триггерах, счетчиках и регистрах, равных нулю. Запоминающие устройства, которые должны начинать работать с других исходных значений, будут установлены в них специальными сигналами.





^ Рисунок 6 – Структурная схема устройства нумерации двоичных чисел на основе многозначных биномиальных чисел


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

  • управляющие сигналы «сброс» и «пуск» не должны появляться одновременно, так как триггер управления целесообразно организовывать на асинхронном R-S – триггере;

  • время задержки между этими двумя сигналами при включении устройства должно быть незначительным, но достаточным для срабатывания выбранного триггера. Целесообразно сигнал «пуск» организовать, задержав на (2-3) tзад триггера управляющий сигнал «сброс».

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

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

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

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

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

Для подсчета количественного эквивалента (номера) многозначного би­номиального числа используется выражение кодообразующей функции (1) числа в биномиальной системе счисления с многозначным алфавитом [4]. Эта формула построена по принципу аддитивности, т.е. производит суммирование количественных эквивалентов каждого разряда числа. Например, для биноми­ального числа 3102 и параметров m=10 и k=4 подсчет количественного эквива­лента будет производиться согласно следующей сумме:


.


Это соответствует записи числа в более общей форме:


.


Каждая сумма в предыдущем выражении равна количественному экви­валенту соответствующего разряда многозначного биномиального числа. При подсчете результата первой значение k не изменяется, а с каждым так­том происходит уменьшение на единицу параметра m. Количество таких тактов при неизменяющемся k равно значению соответствующего разряда биномиаль­ного числа (Xi). Для первой суммы X3 =3 и, следовательно, три такта сумми­рования, т.е. три раза необходимо уменьшить значение m. Количество тактов суммирования удобно контролировать уменьшением с каждым тактом значения разряда биномиального числа. При равенстве нулю данного разряда необходимо перейти к следующей сумме . При этом уменьшается на едини­цу значение параметра k, теперь оно равно k-2. Далее необходимо выпол­нить X2 =1 тактов суммирования с k=2 и снова перейти к следующей сумме. Данная процедура повторяется до тех пор, пока не станет равным нулю пара­метр m. Равенство m=0 свидетельствует об окончании преобразования и, как следствие, о том, что сформирован количественный эквивалент (номер) много­значного биномиального числа. Блок-схема приведена на рисунке 5.

Схема узла нумерации биномиальных чисел должна содержать следующие основные узлы:

  • счетчики числа единиц и счетчик длины;

  • формирователь сочетаний;

  • схему сравнения;

  • сумматор-накопитель;

  • регистр биномиального числа.

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

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

Так как длина биномиального числа определяется параметром k, а каждый разряд биномиального числа не может превы­шать значения q=m-k, то источник биномиального числа будет представлять собой параллельное соединение k счетчиков, каждый из которых состоит не менее чем из триггеров. Запись значений параметров в источник биномиальных чисел осуществляется параллельно во все разряды по переднему фронту сигнала «установка начального значения». Одновременно осуществляется запись в счетчик длины начального значения (m-1). В счетчике единиц записано значение (k-1).

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

Рассмотрим работу схемы по тактам.

Такт 1 В счетчике-источнике многозначного биномиального числа запи­сано число, которое необходимо преобразовать в номер. В счетчиках парамет­ров записаны значения (m-1) и (k-1), которые поступают на входы схемы – формирователя числа сочетаний. Формирователь выдает значение , кото­рое в параллельном коде поступает на вход схемы накопителя, состоящей из сумматора и параллельного регистра. Сумматор осуществляет суммирование числа сочетаний, поступающее с выхода формирователя сочетаний на одну группу входов, с содержимым параллельного регистра, с выхода которого запи­санное в нем значение снова поступает по цепи обратной связи на вторую группу входов сумматора. Значение суммы с выхода сумматора появляется на параллельных входах регистра. Управляет записью числа компаратор, который формирует сигнал записи на выходе «>». Появление сигнала логической еди­ницы на данном выходе разрешает запись, соответственно наличие нуля на вы­ходе «>» запрещает запись полученной суммы в выходной регистр, в котором таким способом накапливается сумма и в результате будет получен номер много­значного биномиального числа в степенной – двоичной системе счисления.

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

Значение с выхода формирователя сочетаний поступает на вход нако­пителя, где в первоначальный момент суммируется с содержимым реги­стра, находящимся в состоянии «нуль». Возможность записи этого значения за­висит от значения управляющего сигнала, сформированного на выходе «>» компаратора. Компаратор производит анализ содержимого старшего разряда биномиального числа посредством сравнения его значения, подаваемо­го на одну группу входов, со значением логического нуля, подаваемого посто­янно на вторую группу его входов. Если значение контролируемого разряда биномиального числа не равно нулю, то на выходе «>» компаратора формиру­ется управляющий сигнал, который разрешает запись сформированной суммы в накопителе. Если же значение анализируемого, в данном случае – старшего, разряда многозначного биномиального числа равно нулю, то запись суммы за­прещается нулевым сигналом на выходе «>». Одновременно на выходе компа­ратора «=» формируется управляющий сигнал, который поступает на вычи­тающий вход счетчика разрядов. Содержимое счетчика k уменьшается на еди­ницу, т.е. необходимо осуществить переход к анализу следующего разряда би­номиального числа. Соответственно уменьшенный на единицу код с выхода счетчика разрядов параллельно поступает на входы дешифратора и активизиру­ет следующий, второй выход дешифратора. Этот сигнал является сигналом вы­борки соответствующего (второго) регистра-счетчика многозначного биномиального числа. Таким образом, осуществляется переход к анализу второго разряда биномиального числа. Выполняются все рассмотренные операции со вторым раз­рядом биномиального числа. Далее переходят к следующему разряду. Описан­ная процедура повторяется до тех пор, пока не обнулится счетчик параметра m. Сигнал обнуления счетчика переведет управляющий триггер в единичное состоя­ние и, таким образом, нулевым сигналом со своего инверсного выхода запретит че­рез схему совпадения прохождение импульсов от генератора на входы устрой­ства нумерации. В то же время единичный сигнал с прямого выхода триггера разрешит через схему совпадения импульсам от генератора прохождение на схему формирования многозначного биномиального числа для следующей двоичной комбинации.

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

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


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.


^ СПИСОК ЛИТЕРАТУРЫ


  1. Цымбал В.П. Теория информации и кодирования: Учебник. - 4-е изд., перераб. и доп. - К.: Вища школа, 1992. - 263 с.:ил.

  2. Амелькин В.А. Методы нумерационного кодирования. - Новосибирск: Наука, 1986. – 158с.

  3. Милт Леонард. Рассмотрение возможных способов сжатия изображений // Электроника. – 1993. - №3-4. – С.10-14.

  4. Борисенко А.А., Онанченко Е.Л., Кобяков А.Н. Системы счисления с биномиальным основанием // Вестник СумГУ. – 1994. - №1. – С. 96-101.

  5. Протасова Т.А., Онанченко Е.Л., Калигаева О.А., Калашников В.В., Бугай В.Д. Синтез комбинаторных конфигураций на основе многозначных биномиальных кодов // Вестник СумГУ. – 1997. - №2(8). – С. 103-109.


Поступила в редакцию 5 декабря 2003 г.

Схожі:

Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconСмкэс-2004
Известны системы ограничений для двоичных биномиальных чисел, полученные на основе структурного подхода. Данные системы ограничений...
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconСмкэс-2004 удк 681. 37 Новый метод сжатия на основе биномиальной системы с многозначным алфавитом протасова Т. А., Бражник И. Е., Сумский государственный университет
В работе предлагается новый метод сжатия изображе­ний, основанный на нумерации биномиальных кодов
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconМетоды сжатия и защиты информации на основе биномиальных кодов борисенко А. А., д т. н., проф. Сумский государственный университет е-mail electron@sumdu edu ua
Диапазон этих систем счисления также представляет биномиальный коэффициент. Известно, что множество всех двоичных чисел длины n можно...
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconСжатие двоичных кодов на основе биномиальных чисел
Для сжатия равновесных кодов ранее были предложены простые алгоритмы, кото­рые несложно реализовать аппаратными средствами. При этом...
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconСредняя длина двоичных биномиальных чисел произвольного диапазона кулик И. А., к т. н доц. Сумский государственный университет
И если задача вычисления средней длины указанных чисел для полного диапазона биномиальной системы счисления с параметрами и автором...
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconУдк 621 037. 37 О средней длине двоичных биномиальных чисел
Таким образом, целью данной работы является дальнейшее исследование линейных неравномерных биномиальных чисел. При этом решаемые...
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconУдк 681. 518 Алгоритмы нумерации двоичных чисел с помощью биномиального счёта
Они способны дать больший коэффициент сжатия информации, позволяющий в процессе сжатия находить ошибки используя для этого ключи,...
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconСвойство вложенности двоичных биномиальных систем счисления и. А. Кулик, канд техн наук, доц
С точки зрения практики это позволит, например, разработать адаптивные алгоритмы передачи данных на основе биномиальных кодов
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconФормирование кодов-композиций на основе многозначных биномиальных чисел
Второй, не менее важной проблемой, является проблема достоверности информации, так как появление ошибок может привести к тяжелым...
Метод сжатия двоичных сообщений на основе многозначных биномиальных чисел и устройство для его реализации т. А. Протасова, ст преп iconСложение двоичных чисел Таблица сложения двоичных чисел
Сложение выполняем поразрядно, начиная с младшей цифры. Если получается больше 1, то записывается 0 и 1 добавляется к старшему разряду...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи