Квазиграфический метод преобразования многорядного кода
Методом определено преобразование многорядного кода, набора слагаемых в сумму как заполнение некоторого графического шаблона - матрицы. Результат преобразования равен или включает в качестве составляющего табличное значение суммы, определяемое по количеству заполненных строк шаблона....
Saved in:
| Date: | 2002 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2002
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/6360 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Квазиграфический метод преобразования многорядного кода / В.П. Гамаюн // Комп’ютерні засоби, мережі та системи. — 2002. — № 1. — С. 53-57. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860252240763158528 |
|---|---|
| author | Гамаюн, В.П. |
| author_facet | Гамаюн, В.П. |
| citation_txt | Квазиграфический метод преобразования многорядного кода / В.П. Гамаюн // Комп’ютерні засоби, мережі та системи. — 2002. — № 1. — С. 53-57. — рос. |
| collection | DSpace DC |
| description | Методом определено преобразование многорядного кода, набора слагаемых в сумму как заполнение некоторого графического шаблона - матрицы. Результат преобразования равен или включает в качестве составляющего табличное значение суммы, определяемое по количеству заполненных строк шаблона.
|
| first_indexed | 2025-12-07T18:44:50Z |
| format | Article |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2002, №1 53
Методом определено преобразо-
вание многорядного кода, набора
слагаемых в сумму как заполнение
некоторого графического шабло-
на - матрицы. Результат преоб-
разования равен или включает в
качестве составляющего таблич-
ное значение суммы, определяемое
по количеству заполненных строк
шаблона.
В.П. Гамаюн, 2002
ÓÄÊ 681.3(031)
Â.Ï.ÃÀÌÀÞÍ
ÊÂÀÇÈÃÐÀÔÈ×ÅÑÊÈÉ ÌÅÒÎÄ
ÏÐÅÎÁÐÀÇÎÂÀÍÈß
ÌÍÎÃÎÐßÄÍÎÃÎ ÊÎÄÀ
Обработка многорядных кодов как сложных
структур данных реализуется при решении
задач цифровой обработки сигналов и изо-
бражений, задач линейной алгебры, теле-
коммуникационных задачах, управления в
реальном времени.
Преобразование многорядного кода, кото-
рый определен* как совокупность слагаемых
А1, А 2, А3,.....,А m , удовлетворяющих равен-
ству С= Aj
m∑ j выполняется посредством
реализации определения количества знача-
щих единиц в разрядных срезах и после-
дующим преобразованием нового многоряд-
ного кода в код меньшей размерности и так
далее до получения двухрядного кода, кото-
рый преобразуется в результат. Формирова-
ние разрядных срезов выполняется в соот-
ветствии с позиционным представлением
каждого слагаемого *. Минимальное количе-
ство разрядов для изображения поразрядной
суммы в двоичной системе счисления
определяется как m' = log 2 (m+1). После
первого шага вычисления многорядного ко-
да, в котором реализуется наибольшее по
критерию уменьшения размерности исходно-
го кода преобразование, в каждом разряд-
ном срезе получена сумма единиц S i. На-
пример, при 16 - разрядной сетке многоряд-
ного кода возможны следующие значения
* Г а м а ю н В.П. Способ ускоренного преобразо-
вания многорядного кода в однорядный // УСиМ. −
1995. − № 4-5. − С.10 -14.
В.П. ГАМАЮН
Комп’ютерні засоби, мережі та системи. 2002, №1 54
в разрядных срезах при количестве слагаемых 16:
11 16 5 12 4 8 10 4 12 5 6 8 0 10 15 7.
Дальнейшее преобразование многорядного кода m' , реализуемое так же, как
и первый шаг, является малоэффективным, так как значения m' и m'' отличают-
ся незначительно.
Предлагаемый метод заключается в выравнивании количества единиц в
разрядных срезах и использовании табличного значения - суммы по всем раз-
рядным срезам с одинаковым количеством единиц при вычислении конечного
результата.
Если после выравнивания в разрядных срезах получены следующие значе-
ния 7 8 8 8 8 7 7 8 , что может быть интерпретировано как графическая
структура
0 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
и, исключая значения равные 7 (некоторый шаблон высотой в 7 единиц), полу-
чаем код 0 1 1 1 1 0 0 1, который суммируется с табличным значением
(1 1 1 1 1 1 1 1)*7 . Результат сложения равен 1 1 1 0 1 1 1 0 0 1 0. Так как в
методе использован факт заполнения некоторого графического шаблона, то
предлагаемый метод назван квазиграфическим.
Выравнивание значений в разрядных срезах можно выполнить по следую-
щему алгоритму: каждое число в позиционной форме записи можно предста-
вить в виде последовательности цифр с выполнением условия переноса в млад-
ших разрядах.
Пусть в первом разрядном срезе - старшем разрядном срезе многорядного
кода получено некоторое значение S1, которое можно представить в заданной
разрядной сетке многорядного кода одинаковыми количествами Е. Для того,
чтобы определить значения Е, необходимо решить следующее уравнение:
S1 = Е +Е*2-1 +Е*2-2 +Е*2 -3 +Е*2-4 +...+Е*2-n , где n - разрядность.
При определении Е для количества единиц в третьем разрядном срезе не-
обходимо решить уравнение
S3 = 4*E +2* Е +E+ Е*2-1 +Е*2-2 +Е*2 -3 +Е*2-4 +...+Е*2-n +2 .
Для вычисления Е для любого разрядного среза решается уравнение
Sk = 2k-1*Е +...+E+E*2-1 +Е*2-2 +Е*2 -3 +Е*2-4 +...+Е*2-n+ k-1 .
Пусть во втором разрядном срезе получено значение 14 и его следует пред-
ставить в 7 - разрядной сетке. Решая уравнение относительно Е
14= 2*Е+Е+Е*2-1+Е*2-2+Е*2-3+Е*2-4+Е*2-5 ,
получаем Е = 3 и остаток, равный 67.
КВАЗИГРАФИЧЕСКИЙ МЕТОД ПРЕОБРАЗОВАНИЯ МНОГОРЯДНОГО КОДА
Комп’ютерні засоби, мережі та системи. 2002, №1 55
Учитывая значение Е и остаток, получаем представление для 14 в 7-раз-
рядной сетке 3 3 3 3 3 3 3 = 4 3 3 3 3 4 4.
1 1 1
В табл.1 приведены примеры представления различных чисел, соответст-
вующих количеству единиц в разрядных срезах. Здесь разложение числа на рав-
ные количества не зависит от величины разрядной сетки.
ТАБЛИЦА 1. Примеры представления чисел
Значение
Числа
Позиция разрядной сетки представления
1-я позиция 2-я позиция 3-я позиция
1 10000...0000 01000..000000 0010000..000
2 11111...1112 100000...0000 01000...00000
3 2111....11112 110000...0000 01100...00000
4 22222...2232 111111.......12 100000..00000
5 322.......2232 121....1111112 10100..000000
..... ................ ............. ............
11 65555....5656 3322..........232 12211...11112
16 8888....89888 444444....4544 2222222.....232
24 12 12...12 13 13 12 12 666...6666776 33333...33334
32 16 16 ..16 17 16 16 16 888888....89888 444444...4544
64 32 32 33 32 .. 32 32 16..16 17 16 16 16 16 888888..89888
При решении уравнения Sk = 2k-1*Е +.....+E+E*2-1 +Е*2-2 +Е*2 -3 +Е*2-4 +
+...+Е*2-n+ k-1 сумма коэффициентов при фиксированных размерностях разряд-
ной сетки и номера разрядного среза остается фиксированной, и решение урав-
нения можно реализовывать с использованием данных из табл.2, в которой при-
ведены значения коэффициентов разложения. Каждый коэффициент разложения
определяется как сумма показателей степени двойки в зависимости от номера
разрядного среза и разрядности представления.
ТАБЛИЦА 2. Коэффициенты разложения при разрядной сетке n=8 и n=16
Величина
разрядной
сетки
Значения коэффициентов
8 1.992188 3.984345 7.96875 15.9375 31.875 63.75 127.5 255
16 1.999969 3.999939 7.999878 15.99976 31.99951 63.99902 127.998 255.9961
511.9922 1023.984 2047.964 4095.938 8191.875 16383.75 32767.5 65535
В.П. ГАМАЮН
Комп’ютерні засоби, мережі та системи. 2002, №1 56
Рассмотрим технологию получения равного количества по разрядным сре-
зам для 12 - разрядного кода со следующими значениями по разрядным срезам
после первого этапа преобразования многорядного кода:
8 12 4 2 2 8 2 2 0 4 8 9
Разложение каждого значения на равные количества дает следующие ре-
зультаты:
Е8 4 4 4 4 4 4 4 4 4 5 4 4
Е12 3 3 3 3 3 3 3 3 3 3 4 4
Е4 1 0 0 0 0 0 0 0 0 0 0 0
Е2 0 0 1 0 0 0 0 0 0 0 0 0
Е2 0 0 0 1 0 0 0 0 0 0 0 0
Е8 0 0 1 0 0 0 0 0 0 0 0 0
Е2 0 0 0 0 0 1 0 0 0 0 0 0
Е2 0 0 0 0 0 0 1 0 0 0 0 0
Е0 0 0 0 0 0 0 0 0 0 0 0 0
Е4 0 0 0 0 0 0 0 1 0 0 0 0
Е8 0 0 0 0 0 0 0 1 0 0 0 0
Е9 0 0 0 0 0 0 0 0 1 0 0 1
Выполнение повторного вычисления по разрядным срезам определяет зна-
чения
8 7 9 8 7 8 8 9 8 8 8 9.
Вычеркивание (вычитание) минимального значения по всем разрядным сре-
зам определяет остаток
1 0 2 1 0 1 1 2 1 1 1 2.
В полученном остатке только два значения должны быть интерпретированы
как двухрядный код, и поэтому окончательное сложение следует реализовать на
трехвходовом сумматоре.
Примеры преобразования для различных значений разрядных срезов приве-
дены в табл.3.
ТАБЛИЦА 3. Результаты преобразования кодов с выравниванием
Исходные значения 0 10 9 4 6 14 14 14
Результат преобразования 4 4 6 6 6 5 5 4
Исходные значения 9 8 14 12 8 10 2 12 14 8 9 10 16 0 9 10
Результат преобразования 10 10 8 7 9 10 9 9 9 7 9 8 8 8 10 8
Исходные значения 8 10 14 2 12 6 12 10 10 6 14 4 12 10 0 0
Результат преобразования 9 9 9 9 10 8 8 10 9 10 9 7 8 8 8 8
КВАЗИГРАФИЧЕСКИЙ МЕТОД ПРЕОБРАЗОВАНИЯ МНОГОРЯДНОГО КОДА
Комп’ютерні засоби, мережі та системи. 2002, №1 57
Этапы метода квазиграфического преобразования многорядного кода:
1) определение количества единиц по разрядным срезам (временные затра-
ты Тпр);
2) разложение каждого значения разрядного среза на одинаковые, равные
количества по разрядной сетке многорядного кода (Тр);
3) повторное определение количества единиц по разрядным срезам;
4) определение минимального значения в разрядных срезах и формирова-
ние составляющего результат слагаемого - кода шаблона (временные затраты на
этот этап Тш);
5) окончательное суммирование кода шаблона и остатка, полученного по-
сле "вычеркивания" шаблона.
Временные затраты на преобразование многорядного кода по методу квази-
графического преобразования определяются как
Т мн = 2*Тпр + Тр + Тш + Тсл .
Реализация преобразователя с использованием ПЛИС технологий опреде-
ляет величину Т мн для многорядного кода размерностью m = 16-128 как
8-12 нсек, что соответствует уровню производительности 1- 1.5*109 операций/с.
Такой преобразователь, работающий по предложенному методу, может най-
ти применение в составе спецпроцессора, сопроцессора в системе цифровой об-
работки сигналов и изображений, систем управления в реальном времени, уст-
ройствах автоматики, в качестве составляющего компонента функционально-
процессорного поля или как часть операционной среды СуперЭВМ.
Получено 01. 07. 2002
|
| id | nasplib_isofts_kiev_ua-123456789-6360 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1817-9908 |
| language | Russian |
| last_indexed | 2025-12-07T18:44:50Z |
| publishDate | 2002 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Гамаюн, В.П. 2010-03-01T16:34:17Z 2010-03-01T16:34:17Z 2002 Квазиграфический метод преобразования многорядного кода / В.П. Гамаюн // Комп’ютерні засоби, мережі та системи. — 2002. — № 1. — С. 53-57. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/6360 681.3(031) Методом определено преобразование многорядного кода, набора слагаемых в сумму как заполнение некоторого графического шаблона - матрицы. Результат преобразования равен или включает в качестве составляющего табличное значение суммы, определяемое по количеству заполненных строк шаблона. ru Інститут кібернетики ім. В.М. Глушкова НАН України Квазиграфический метод преобразования многорядного кода Article published earlier |
| spellingShingle | Квазиграфический метод преобразования многорядного кода Гамаюн, В.П. |
| title | Квазиграфический метод преобразования многорядного кода |
| title_full | Квазиграфический метод преобразования многорядного кода |
| title_fullStr | Квазиграфический метод преобразования многорядного кода |
| title_full_unstemmed | Квазиграфический метод преобразования многорядного кода |
| title_short | Квазиграфический метод преобразования многорядного кода |
| title_sort | квазиграфический метод преобразования многорядного кода |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6360 |
| work_keys_str_mv | AT gamaûnvp kvazigrafičeskiimetodpreobrazovaniâmnogorâdnogokoda |