Устройство подсчета кодов Советский патент 1990 года по МПК G06F7/06 G06F17/40 

315

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

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

На фиг.1 представлена функциональная схема устройства; на фиг.2 - функциональная схема узла формирова- ния адреса; на фиг.З - пример реализации первого блока памяти; на фиг. - пример реализации второго бло

ка памяти; на фиг.5 - пример реализации счетчика импульсов; на фиг.6 - основные способы подачи кодов при подсчете.

Устройство содержит узел 1 формирования адре са, первый и второй блоки 2 и 3 памяти, счетчик k импульсов, счетчик 5 страниц, счетчик 6 групп, счетчик 7 подмассивов, информационные вход 8 и выход 9, адресный вход 10, счетные входы 11-И, вход 15 записи, вход 16 управления, вход 17 записи, вход 18 чтения-записи, входы 19-21 записи, шину 22 данных, выход 23 конца обработки, выход требования загрузки и выход 25 конца обработки.

Узел 1 (фиг.2) содержит регистр 26 адреса, мультиплексор 27, вход 28 записи и вход 29 управления.

Регистр 26 предназначен для временного хранения данных, принятых с входа 8. Мультиплексор преобразует Ьк-разрядный код данных в группу LK/g разрядов (g - число групп, на которое делится код), которую передает на

40

В зависимости от способа подачи кодов несколько изменяется последовательность подачи управляющих сигналов. Каждый импульс (фиг.6) идентифицирует код произвольной величины в диапазоне от нуля до 2 к-1. На фиг.ба коды 11, 12,...,1G образуют первый

вход младших разрядов адресного входа д подмассив, коды 21, 22,...,2G - второй подмассив, коды PI, P2,...,PG - Р-й подмассив из G кодов. Таким образом, первые цифры указывают порядковый номер подмассива, вторые - число

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

Блок 2 памяти (фиг.З) предназначен

для записи, хранения и считывания ре- JQ кодов в подмассиве. На фиг.бб послезультатов подсчета. Результаты подсчета в каждом наборе одноименных кодов сохраняются в одной из страниц блока 2, число которых определяется разрядностью счетчика 5. Число ячеек Внутри страницы K определяется Разрядностью кода. Адрес ячейки определяется величиной кода на выходе 1.

55

довательность цифр в обозначении кодов, та же, но из последовательности кодов видно: вначале подается набор из всех первых кодов каждого подмассива, .затем набор из всех вторых кодов и последним набор из всех G-x кодов. Таким образом, число наборов одноименных кодов равно числу кодов в одном подмассиве.

$

0

5

0

0

Выходы элементов 30 памяти (фиг.З) объединены по монтажному ИЛИ и образуют первый разряд блока 2 памяти. Аналогично элементы 31 и 32 памяти образуют второй и L-й разряды блока 2 памяти соответственно.

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

Счетчик 4 импульсов (фиг.5) предназначен для приема содержимого блока 2 памяти, увеличения его на единицу и передачи на информационный вход блока 2 при подсчете либо для передачи содержимого блока 2 памяти на информационный выход 9 при считываний результатов. Счетчик импульсов может быть реализован на элементах З счетного типа, содержащих один или несколько разрядов.

Счетчики 5 - 7 предназначены для приема, хранения и модификации на единицу адреса начальной страницы, числа групп разрядов (кодов) и числа подмассивов соответственно. Эта служебная информация поступает с блока 3 памяти по шине 22 данных.

В зависимости от способа подачи кодов несколько изменяется последовательность подачи управляющих сигналов. Каждый импульс (фиг.6) идентифицирует код произвольной величины в диапазоне от нуля до 2 к-1. На фиг.ба коды 11, 12,...,1G образуют первый

кодов в подмассиве. На фиг.бб после

довательность цифр в обозначении кодов, та же, но из последовательности кодов видно: вначале подается набор из всех первых кодов каждого подмассива, .затем набор из всех вторых кодов и последним набор из всех G-x кодов. Таким образом, число наборов одноименных кодов равно числу кодов в одном подмассиве.

Для надежной работы необходимо выдерживать следующие требования:

.

Ck п., С 1А + -6П2

С ml vi - LH т .п

де

„;,+ V

/

Ь.

гг

л

Ci

А,

Vfll

время между подачей соседних кодов в одном подмассиве; время между соседними под- массивами;

время между соседними наборами одноименных кодов; время задержки кодов в узле 1 адреса;

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

6nj время операции Чтение-моди- 15 « приему и обработке следующего кода.

Второй код первого подмассива веРг

фикация-запись в блоке 2 и счетчик ;

время загрузки счетчиков 5 - 7 с блока 3 памяти. Работу устройства вначале рассмот- Q РИМ на примере подсчета кодов в под- массивах, поступающих последовательно в соответетвии с фиг,6а.

В исходном состоянии все страницы

личиной 1

ii

принятый в

вится адресом ячейки j.

узел . Но

1, стано- так как

содержимое счетчика 5 увеличено, то ячейка i будет читаться из следующей страницы, а ее содержимое (первый раз равное нулю) принимается в счетчик k, увеличивается на единицу и записывается в ячейку 1,2. считанной

содержимое счетчика 5 увеличено, ячейка i будет читаться из следу страницы, а ее содержимое (первый раз равное нулю) принимается в сч чик k, увеличивается на единицу и писывается в ячейку 1,2. считанной

30

35

блока 2 памяти, которые будут исполь- 25 страницы. После этого содержимое зеваться при обработке конкретного массива, обнулены. В определенные ячейки блока 3 памяти (задаваемые на адресном входе 10) должны быть записаны: адрес начальной страницы, число групп разрядов (кодов) в подмассиве и число подмассивов в обрабатываемом массиве. Запись осуществляется с входа 8 по сигналу записи на входе 18. Затем эта служебная информация переписывается в счетчики 5 - 7 по сигналам записи на входах 19-21 соответственно. Если содержимое счетчиков 6 и 7 задано в дополнительном коде, то счетные входы должны выполнять 40 +1, если в прямом коде, - то -1. Первый код первого подмассива величиной 14( принимается с входа 8 в узел 1 по сигналу записи на входе 15. Код данных, принятый в узел 1, посту- 45 пает на младшие разряды адресного входа блока 2 памяти, становится таким образом адресом ячейки 11(. Старшая часть адреса, указывающая первую заданную страницу, поступает в блок 2 памяти из счетчика 5. При наличии разрешения чтения на управляющем вхо50

счетчика 5 увеличивается на едини а содержимое счетчика 6 уменьшает на единицу.

Третий, четвертый, ..., G-й ко первого подмассива обрабатываются аналогично. Каждый новый код перв подмассива увеличивает на единицу держимое ячейки, равное по величи поступившему коду данных, но кажд раз в новой странице. После обраб последнего G-го кода первого подм сива на выходе счетчика 6 появляе сигнал переполнения. Он вызывает уменьшение содержимого счетчика 7 на единицу и инициирует через вых 2 последовательность управляющих сигналов по загрузке адреса начал страницы в счетчик 5 и число набо одноименных кодов (число групп в массиве) в счетчик 6 из ячеек бло 3 памяти. Для этого на адресном вх 10 задаются адреса хранения соотве ствующих кодов. По сигналам Чтени на входе 18 и Запись на входах и 20 с блока 3 памяти записывается счетчики 5 и 6 необходимая информа ция.

де 16 содержимое ячейки i (( (первый раз равное нулю) начальной страницы считывается с блока 2 и записывается в счетчик по сигналу записи на входе 17. В счетчике 4 содержимое ячейки i,, увеличивается на единицу по счетному входу 11, а затем новое

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

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

личиной 1

ii

принятый

вится адресом ячейки

содержимое счетчика 5 увеличено, то ячейка i будет читаться из следующей страницы, а ее содержимое (первый раз равное нулю) принимается в счетчик k, увеличивается на единицу и записывается в ячейку 1,2. считанной

страницы. После этого содержимое

30

35

25 страницы. После этого содержимое 40 5

0

5

счетчика 5 увеличивается на единицу, а содержимое счетчика 6 уменьшается на единицу.

Третий, четвертый, ..., G-й коды первого подмассива обрабатываются аналогично. Каждый новый код первого подмассива увеличивает на единицу содержимое ячейки, равное по величине поступившему коду данных, но каждый раз в новой странице. После обработки последнего G-го кода первого подмассива на выходе счетчика 6 появляется сигнал переполнения. Он вызывает уменьшение содержимого счетчика 7 на единицу и инициирует через выход 2 последовательность управляющих сигналов по загрузке адреса начальной страницы в счетчик 5 и число наборов одноименных кодов (число групп в под- массиве) в счетчик 6 из ячеек блока 3 памяти. Для этого на адресном входе 10 задаются адреса хранения соответствующих кодов. По сигналам Чтение на входе 18 и Запись на входах 19 и 20 с блока 3 памяти записывается в счетчики 5 и 6 необходимая информация.

Первый код второго подмассива ве- . личиной i, принимается с входа 8 в узел 1. Так как в счетчике 5 снова находится адрес первой заданной (начальной) страницы, то код г,адресует ячейку в той же странице, что и код

Liir

Обрабатывается он аналогично кодам первого подмассива. Если ,, i, то содержимое ячейки i становится равным двум. Если ij,i,,, то содержимое некоторых двух ячеек становится равным единице. После учета кода 1ц в ячейке i2 начальной страницы блока 2 содержимое счетчика 5 увеличивается, а счетчика 6 уменьшается на единицу. Второй, третий,...,С-тые коды второго подмассива обрабатываются аналогично. Каждый код подмассива учитывается в ячейке блока 2 памяти своей страницы благодаря модификации счетчика 5 в каждом цикле обработки очередного кода. После обработки последнего С-го кода второго подмассива на выходе счетчика 6 появляется сигнал переноса, что вызывает уменьшение содержимого счетчика 7 на единицу и перезагрузку содержимого счетчиков 5 и 6. После обработки последнего кода последнего подмассива импульс переполнения появляется на выходе 25 счетчика 7, который информирует о конце обработки всего массива данных. К этому моменту в начальной странице блока 2 памяти будут результаты подсчета кодов в наборе, образованном первыми кодами каждого подмассива, - во второй странице - результаты подсчета в наборе, образованном вторыми кодами каждого подмассива, а в 0-й странице - результаты подсчета в наборе, образованном G-ми кодами каждого подмассива. При этом в ячейке О каждой страницы указано число величиной 0 в первом наборе, в ячейке 1 - число кодов величиной 1, в ячейке 2 - число кодов величиной 2, а ч ячейке 2.-1 записано число кодов величиной

,U

-1.

Работа устройства при обработке кодов, поступающих в соответствии с фиг.бб, осуществляется следующим образом.

Перед началом работы в блоке 2 памяти должны быть обнулены G страниц, начиная с первой заданной, и в определенные ячейки блока 3 памяти должна быть записана служебная информация: адрес начальной страницы, число кодов в подмассиве и число подмассивов в обрабатываемом массиве. Затем адрес начальной страницы загружается в счетчик 5, как и в первом примере, число кодов в подмассиве загружается в счетчик 7, а число подмассивов - в счетчик 6. Таким образом, при изме

0 5 о Q

5

5

5

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

Первый код первого подмассива обрабатывается так же, как и в первом примере, т.е. принимается в узел 1 и становится младшей частью адреса блока 2. Старшая часть адреса поступает из счетчика 5. Содержимое ячейки i(1 начальной страницы считывается, увеличивается на единицу в счетчике , и новое значение записывается в ту же ячейку начальной страницы. Так как коды, поступающие в счетчик кодов, являются первыми кодами (первым набором) из каждого подмассива, то после учета первого кода содержимое счетчика 5 не изменяется и следующий код величиной Ј,, адресует ячейку в той же начальной странице. Содержимое счетчика 6 уменьшается на единицу и указывает, что в первом наборе осталось обработать Р-1 код. Аналогично после обработки третьего, четвертого, ..., Р-го кодов содержимое счетчика 5 не изменяется и величина всех Р кодов учитывается в начальной странице. В счетчике 6 после обработки последнего Р-го кода первого набора возникает импульс переполнения, который уменьшает содержимое счетчика 7 на единицу, увеличивает содержимое счетчика 5 на единицу.

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

Узел 1 формирования адреса (фиг.2) работает следующим образом.

Если возникает переполнение на выходе 23, то это служит сигналом прекращения операций подсчета. При приеме кода данных с входа 8 через вход 15 на вход 28 записи регистра 26 адреса подается строб записи, а на вход управления мультиплексора 27 подаются сигнал разрешения передачи и код выбора направления.

Предложенная реализация узла 1 позволяет значительно уменьшить объем используемой памяти, если коды на входе 8 многоразрядные (8-32 и более разрядов), а составные части кодов независимы (например, 1«-8-раз- рядные цифры, буквы, символы и так далее). В этом случае для подсчета в том же массиве требуется g-(2 )

ячеек вместо ячеек, где g - коэффициент мультиплексированияj Lк разрядность кода на входе 8. Упорядоченные по величине кода результаты подсчета в одном, нескольких или во всех наборах одноименных кодов могут быть считаны и переданы в память другого устройства или ЭВМ.

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

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

5

0

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

Изобретение относится к вычислительной технике и может быть использовано в устройствах сбора, подсчета и сортировки информации. Цель изобретения - расширение области применения за счет возможности подсчета кодов в различных множествах входных данных. Устройство содержит узел 1 формирования адреса, блоки 2 и 3 памяти, счетчик 4 импульсов, счетчик 5 страниц, счетчик 6 групп и счетчик 7 подмассивов. Коды для подсчета поступают по входу 8 в узел 1, и в соответствующей ячейке блока 2 памяти содержимое увеличивается на единицу. Выбор ячейки блока 2 памяти зависит от вида распределения входной информации. 6 ил.

блока памяти, первый и второй счетные 25 нения счетчика групп соединен со

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

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

51

i

ж

§

ft

5) Ч

CM

s ft

2Пф

LSwMl

Порядковый номер подмассива

п

Г 1-й подмассив

21 П- Рг Рб

П-JI-JL-JT JI--.JL

Z-uподмоссив

Р-и подмассив

Порядковый номер подмассива

Г/т

К 22Г . 26

ПП...

/.

/.

12

1t2... 6-тыи набор одноименных кодов

V

Все коды одного под/массива (массива)

Фиг. 6

Порядковый номер кода В под мае с иве

Р-и подмассив

Порядковый номер кода в подмассиве

Г . 26

...

/.

2