Устройство для приведения р-кодов фибоначчи к минимальной форме

Авторы патента:

H03M7/30 - уплотнение (анализ-синтез речи для сокращения многословия или избыточности G10L 19/00; для передачи изображения H04N); расширение; подавление излишней информации, например сокращение избыточности

Изобретение относится к вычислительной технике и может быть использовано для приведения кодовых слов к минимальной форме изображений в базисе P-систем счисления Фибоначчи, а также выполнять функции счетчика. С целью расширения функциональных возможностей за счет способности приводить к минимальной форме кодовые слова при P*982 устройство содержит в каждом разряде триггер 1, элементы ИЛИ 2 и 3, с первого по P-й элементы И 4-6, элемент НЕ 7, с первого по (P-1)-й элементы 8,9 запрета с соответствующими связями. 1 ил.

СОЮЗ СОВЕТСКИХ

COLIHAËÈÑÒÈ×ЕСКИХ

РЕСПУБЛИК (19) (11) А1 (51)5 Н 03 М 7/30

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

OCV4APCTBEHHblA HOMHTET

ПО ИЭОБРЕтЕНИЯМ И ОТКРМТИЯМ

ПРИ ГННТ СССР

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4412455/24-24 (22) 18.04 ° 88 (46) 28.02.90. Бюп. N 8 (71) Кубанский государственный университет (72) В.В. Дудкин и Н.А. Яковенко (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

У 1392554, кл. Н 03 М 7/30, 1926.

Авторское свидетельство СССР

1(662930, кл. Н 03 М 7/30, 1976. (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КОДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ. (57) Изобретение относится к вычислиг тельной технике и может быть использовано для приведения кодовых слов к минимальной форме изображений в базисе р-систем счисления Фибоначчи, а также может выполнять функции счетчика. С целью расширения функциональных возможностей за счет способности приводить к минимальной форме кодовые слова при р р 2 устройство содержит в.каждом разряде триггер 1, элементы

ИЛИ 2 и 3, с первого по р-й элементы

И 4-6, элемент НЕ 7, с первого по (р-1)-й элементы 8, 9 запрета с соответствующими связями. 1 ил.

3 15470 (Изобретение относится к вычислительной технике и может быть использовано для приведения кодовых слов к минимальной форме изображений в

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

Цель изобретения - расширение функциональных возможностей за счет спо- 10 собности приводить к минимальной фор1 ме кодовые слова при p > 2.

На чертеже представлена схема разряда устройства для приведения р-кодов Фибоначчи к минимальной форме.

Разряд устройства содержит триггер

1, первый и второй элементы ИЛИ 2 и

3,, с первого по р-й элементы И 4-6, элемент НЕ 7, с первого по (р-1)-й элементы 8 и 9 запрета, вход 10 разряда информационного входа устройства, вход 11 сброса устройства, группу входов 12 запуска устройства, входы

13-21 и выходы 22-25 разряда устройства. 25 р-Системы счисления Фибоначчи задаются рекурентным выражением

О, при п(0;

g(п)= 1, при О <и <р; (1)

P K q(n-р-j), при и ) р, 30 где q (n) вЂ” имя системы счисления;

n вЂ” номер текущего разряда (и = 0,1,2,...N). р вЂ” номер системы счисления (р = 0,1,2,...,и, в общем 35 случае п Ф р) .

Операция приведения р-кодов к минимальной форме описывается выраже нием: н

Epp(n-1 ) + Pp(n-p-1+N) = @p(i) + qp(n-Zp-1+И-i) (2) где N = 1,. ° .,(р-1).

В основу операции свертки положено 45 равенство единице содержимого триггеров 1 (r-1)-ro и (r-p-1+Щ-го разрядов: Q(r-1) =.Q(r-р-1+И) =1; ! равенство нулю содержимого триггеи

50 ров r-го и K (r-Zp-1+14-j)-х разря1= И дов: Q (r) =Q (" (r-2р-1+N- j )) == О.

1=4

После выполнения операции свертки

Q(r-1) = Q(r-р-1+N) = О;

Q(r) = ((; (r-2р-1+N-j)) == 1.

J-<

Устройство работает следующим образом.

Снятие напряжения "1" с входа 12 разрешает работу устройства. Допустим, что на вход 21 пришли все единичные сигналы. Это свидетельствует о и том, что триггеры 1 K (r-2р-1+И-j)-x ,/а 1 разрядов находятся в нулевом состоянии. Пусть триггер l рассматриваемого разряда также находится в нулевом состоянии, а триггер 1 (r-1)-го разряда вЂ” в единичном, что приводит к появлению на всех входах элемента

И 6 сигналов "1". Единичный сигнал с выхода элемента 9 запрета закрывает элемент Иб и элемент 8 запрета, а через элемент НЕ 7 вЂ” элемент И4.

Сигнал "1" с выхода элемента Иб через элемент KIN 3 устанавливает триггер 1 в единичное состояние,сбрасывает через выходы 22 и 25 триггеры

1 соответственно (r-p-1+14)-ro u (r-1)-ro разрядов, устанавливает в единичное состояние через выходы 23„ и триггеры 1 Е (r-2р-1+и-j)-х разрядов.

I- 1

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

В случае, если на входе 21 присутствует хотя бы один сигнал "О", на выходе элемента 9 запрета появляется нулевой сигнал, который закрывает элемент Иб, но открывает элемент 8 запрета. Если на входах 20 элемента

8 запрета присутствуют сигналы "1", то происходят аналогичные описанные выше для элемента 9 запрета переключения. Если же на входе 20 присутствует хотя бы один нулевой сигнал, то на выходе элемента 8 запрета появляется сигнал, разрешающий анализ состояния входов 14 и 15. Если же и на них нулевой сигнал, то изменений в

r-м разряде не происходит, но они

1происходят в других разрядах анало гично описанному для r-го разряда.

Пример, Привести к минимальной форме изображений (представлений) кодовое слово в 3-системе счисления

Фибоначчи.

Операции свертки описываются соотношениями, вытекающими иэ выражения:

5 п01 2345678 9 1 у (п) 1 1 1 1 2 345 7+0+4

Опеоооо 0 0 0 » 0 0 0 1 0

000001 001 О 1

15470

О 11

00001 1 000 О О 1

100000100 0 О

000100100 0 0

Итого О О О О О О О 1 0 0 О 1

1! 1411 t

Равенство нулю веса отрицательных разрядов делает ненужным их использование, однако связи положительных

При опросе разрядов, начиная со старших, условия свертки выполняются только в пятом разряде. В одиннадцатом разряде этого не происходит в силу того, что перенос в четвертый разряд запрещен наличием в нем "1". Это 20 приводит к тому, что на выходе элемента 8 запрета одиннадцатого разряда присутствует нулевой сигнал. В пятом разряде на входах элемента И 6 имеются четыре единичных сигнала: с инверсного выхода триггера 1 своего разряда, с прямых выходов триггеров

1 четвертого и третьего разрядов и с выхода элемента 9 запрета, так как в входы его подключены к триггерам 1 отрицательных разрядов, следовательно, на них имеются "1 . Единичный сигнал с выхода элемента И 6 через элемент ИЛИ З устанавливает триггер

1 пятого разряда и сбрасывает через элементы ИЛИ 2 в "О" триггеры 1 третьего и четвертого разрядов. Следующий опрос приводит к тому, что в одиннадцатом разряде на выходе элемента И5 появляется "1", так как на его входе имеется "1" с инверсного выхода триггера t одиннадцатого разряда„ с.прямых выходов триггеров 1 десятого и восьмого разрядов и с выхода элемента 8 запрета. Это приводит к тому, что в единичное состояние устанавливают через элементы

ИЛИ 3 одиннадцатого и.четвертого раз.рядов соответствующие им триггеры 1.

Следующей выполняется операция свертки в шестом разряде аналогично опи50 санному для пятого. Перенос "1" из нулевого разряда описан выше. Для седьмого разряда вЂ” аналогично одиннадцатому разряду.

73 6

Разрядов с отрицательными надо оставить. Это означает, что на входах 14, 15, 16, 17, 20 и 21, "соединенных" с соответствующими. отрицательными

1 разрядами, присутствует постоянное напряжение "1",выходы 22 и 23, идущие в отрицательные разряды, заземлены.

Рассмотрим механизм переноса "1" из нулевого разряда в третий. Опрос входов 12, начиная со старших разрядов, приводит к тому, что в первом разряде на входах элемента 9 запрета появляются логические единичные сигналы (на его входах 2 1, идущих в отрицательные разряды, присутствует постоянный сигнал "1"). Это приводит к появлению "1" на выходе элемента

И6, так как íà его входах имеется "1" с инверсногс выхода триггера первого разряда, с прямых выходов триггеров нулевого и минус первого разрядов.

Единичный сигнал через элемент ИЛИ 3 устанавливает в единичное состояние триггер 1 первого разряда и сбрасывает в нулевое состояние триггер нулевого разряда. Появление "1" в первом разряде приводит к следующим процессам во втором разряде. Элемент 8 запрета заперт сигналом с выхода элемента 9 запрета. Следовательно, единичный сигнал на выходе элемента НЕ 7 приводит к появлению "1" на выходе элемента И4, так как на его входах присутствуют 1 с инверсного выхода второго разряда, с прямых выходов первого и минус второго разрядов с .. выхода элемента НЕ 7. Это приводит к установке в единичное состояние триггера 1 второго разряда и обнулению триггера 1 первого разряда. Появление единичного сигнала во втором разряде приводит к аналогичному процессу в третьем разряде, результатом которого является установка в единичное состояние триггера 1 третьего разряда и обнуление триггера l,нулевого разряда. Таким образом, происходит перенос "1" из нулевого разряда в третий разряд. Появление второй "1" на входе 10 нулевого разряда приводит в четвертом разряде к процессу, схожему с процессом, описанным для второго разряда, результатом которого является установка в единичное состояние триггера 1 четвертого разряда и обнуление триггеров 1 третье1547073

3 4 5 б

1 2 3 4

О О О О

О О 0 О

О О О О

1 О О О

1 U О О

О 1 О U

О 1 0 О

О О 1 О

О О 1.0

О О 1. О

О 0 1 О

О О О 1

-3 -2 -1 О 1 2

О О О 1,1 1

1 О О

О 1 О

О О 1

О О О

1 О О

О О О

1 О О

0 1 О

О О О

1 О О

О 1 О

О О 1

О О О

7 8

5 7 10

О О О

О 0 О

О О О

0 О О

О 0 О

О О О

О О О п

° ° °

LP> (и) ввод ."1"

Вво «1"

Ввод "1

Ввод "1"

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

Формула изобретения

Устройство для привецения р-кодов

Ф боначчи к минимальной форме,содержащее в каждом r-м разряде триггер, 25

Первый элемент И, первыи и второи элементы ИЛИ, элемент НЕ, причем к1ходы разрядов информационного входа устройства соединены с первыми вхоами вторых элементов ИЛИ соответтвующих разрядов устройства, выходы 39 которых соединены со счетными входами триггеров соответствующих разрядов и устройства, входы установки в О оторых соединены с выходами перых элементов ИЛИ соответствующих азрядов устройства, первые входы которых объединены и соединены с входом сброса устройства, инверсные выходы триггеров разрядов устройства соединены с первыми входами первых элементов.И соответствующих разрядов устройства, выходы которых соединены с вторыми входами вторых элементов ИЛИ соответствующих разрядов устройства, второй и третий входы первого элемента И r-го. разряда устройства соединены соответственно с прямыми выходами триггеров (r-1)-ro и (к-р-1)-ro разрядов устройства,четвертые входы первых элементов И разрядов устройства содинены с выходами элементов НЕ соответствующих разрядов устройства, второй и третий входы первого элемента ИЛИ r-ro разряда устройства соединены соответственно с выходами первых элементов И.(r+1)-ro и (r+p+1)-ro разрядов устройства, пря ые выходы триггеров разрядов устройства являются выходами соответствуюторого также поясняется работа устройства в качестве счетчика. ших разрядов устройства, о т и и ч аю щ е е с я тем, что, с целью расши- 1 рения функциональных возможностей за счет способности приводить к минимальной форме кодовые слова при р Ъ 2 к-й разряп устройства содержит с Вто» рого по р-й элементы И и с первого по (р-1)-й элементы запрета, причем выход второго элемента ИЛИ r-ro разряда устройства соединен с четвертым входом первого элемента ИЛИ (r-1)-го разряда устройства, первые входы с второго по р-й элементов И разрядов устройства соединены с инверсными выходами триггеров соответствующих разрядов устройства, вторые входы с второго по р-й элементов И r-ro разряда устройства соединены с прямым выходом триггера (r-1)-го разряда устройства, третий вход (К+1)-го (К = 1,..., р вЂ” i) элемента И r-ro разряда устройства соединен с прямым выходом триггера (r-p-1+К)-го разряда устройства, четвертый вход (К+1)-ro элемента И к-го разряда устройства соединен с выходом К-го элемента запрета r-ro разряда устройства, выход первого элемента запрета

r-го разряда устройства соединен с входом элемента НЕ r-го разряда устройства, выход К-го, кроме первого, элемента запрета r-го разряда устройства соединен с управляющим входом (К-1)-ro элемента запрета r-ro разряда устройства, входы запуска группы устройства соединены с управляющими входами (р-1)-х элементов запрета соответствующих разрядов устройства, выход (К+1)-го элемента и r-го Разряда Устройства соединен с (К+2)-м

154 7073 ветственно (N = 0,1,...,р-1; n =

1,2,...,р; i = 1,2,...,N; iPn), к входам с пятого по (р+1)-й первого

Составитель А. Клюев

Техред Л.Сердюкова

Корректор В. Гирняк

° »

Редактор А. Лежнина

Заказ 85

Тираж 656

Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101 входом второго элемента ИЛИ r-го разряда устройства, выходы с второго по р-й элементов И r-ro разряда устP ройства подключены к; (p+1+n)-м м входам вторых элементов ИЛИ (r-2pi-- 1

-1+0-i)-х разрядов устройства соотэлемента ИЛИ r-го разряда устройства подключены выходы с второго по р-й элементов И. (г+р+1-N)-ro разряда и устройства соответственно X. (и+1)-е

j информационные входы с первого по (р-1)-й элементов запрета r-ro разряда устройства соединены с инверсными и .выходами триггеров X (r-2p-1+N-i)-х

\ » 1 разрядов устройства соответственно.

Устройство для приведения р-кодов фибоначчи к минимальной форме

Похожие патенты:

Преобразователь кодовых форм // 1545329

Изобретение относится к атоматике и вычислительной технике и может быть использовано в гибких АСУ и ЭВМ для проебразования минимальной формы числа в оптимальную форму этого же числа

Устройство для приведения @ -кодов фибоначчи к нормальной форме // 1508351

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

Дифференциальный импульсный кодер телевизионного сигнала // 1481900

Изобретение относится к вычислительной технике и технике связи и может быть использовано в цифровых телевизионных системах

Устройство для перекодирования видеографических матриц 12 @ 10 в матрицы 8 @ 10 // 1479015

Изобретение относится к вычислительной технике

Преобразователь формы кода // 1462491

Изобретение относится к автоматике и вычислительной технике и может быть использовано в гибких АСУ и ЭВМ для преобразования минимальной формы числа в пакетную форму этого же числа

Устройство для преобразования формы кода фибоначчи // 1418910

Изобретение относится к вычис- , лительной технике и может быть использовано в системах обработки и передачи данных для повышения их контролеспособности и надежности эа счет использования свойств так называемой частично развернутой формы кода Фибоначчи

Устройство для сжатия данных // 1012313

Устройство для передачи двоичных сигналов, содержащих избыточность // 374760

Способ передачи информации по четьгрехпроводнойлинии // 294260

Устройство для оценки качества каналов передачи данных // 285039

Способы фрагментирования, анализа структуры и сжатия потока импульсно-сигнальной информации и устройство для их реализации // 2108665

Сжиматель выделяемых символов в двоичной комбинации // 2110832

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

Устройство для выдачи сжатого видеосигнала (варианты) // 2115261

Способ и устройство кодирования и декодирования данных // 2117388

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

Телевизионная система для преобразования сжатых данных, представляющих изображения и размещенных в блоках, в несжатые данные и система для обработки сжатых видеоданных, передаваемых в виде блоков // 2119269

Изобретение относится к системам маскировки видеоданных, которые теряются в процессе передачи

Способ и устройство сжатия символов, стохастический кодер (варианты) // 2125765

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

Способ и система кодирования и способ и система декодирования // 2154350

Способ и устройство сжатия данных с использованием ассоциативной памяти // 2159989

Способ и устройство сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов // 2168857

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

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

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