Многовыходной указатель старшей единицы

Изобретение относится к области вычислительной техники и используется, в частности, для арбитража в системах обработки информации при организации передачи данных между устройствами. Технический результат - расширение функциональных возможностей в части формирования K указателей старших единиц в порядке старшинства приоритетов. Многовыходной указатель старшей единицы содержит группу из N внешних входов запроса Z1, Z2, …, ZN (высший приоритет имеет вход ZN), K каскадов (K - количество формируемых указателей старших единиц) и K групп внешних выходов U указателей старшей единицы, при этом каждый i-й каскад (i=1, 2, …, K) содержит группу из (N-i-1) элементов ИЛИ 1_i1, 1_i2, …, 1_i(N-i-1) и группу из (N-i) элементов запрета И с одним инверсным входом 2_i1, 2_i2, …, 2_i(N-i), а также группу из (N+1-i) входов запроса в i-й каскад A_i1, A_i2, …, A_i(N+1-i) и группу из (N+1-i) внешних выходов указателей старшей единицы i-го ранга U_i1, U_i2, …, U_i(N+1-i) (1-й ранг имеет высший приоритет), каждый из первых (K-1) каскадов, кроме последнего K-го каскада содержит также группу из (N-i) элементов И 3_i1, 3_i2, …, 3_i(N-i) и группу из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад. 1 ил.

 

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

Известны приоритетные шифраторы (Дж. Ф. Уэйкерли. Проектирование цифровых устройств. В 2-х томах. - М.: Постмаркет, 2002. - 1088 с., с. 440-445; Лехин С.Н. Схемотехника ЭВМ. - СПб.: БХВ-Петербург, 2010. - 672 с., с. 213-220; Угрюмов Е.П. Цифровая схемотехника. - СПб.: БХВ-Петербург, 2000. - 528 с., с. 50-53), в которых формируется двоичный код номера устройства старшего приоритета.

Известен двойной приоритетный шифратор (Дж. Ф. Уэйкерли. Проектирование цифровых устройств. В 2-х томах. - М.: Постмаркет, 2002. - 1088 с., рис. 6.6, с. 561-562), содержащий два блока приоритетного шифратора, дешифратор, группу элементов И-НЕ и группу элементов НЕ. Данное устройство определяет не только сигнал с наивысшим приоритетом, но также сигнал «со вторым по старшинству приоритетом».

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

Известен указатель старшей единицы (Угрюмов Е.П. Цифровая схемотехника. - СПб.: БХВ-Петербург, 2000. - 528 с., рис. 2.8 с. 50-54), содержащий группу элементов И и группу элементов запрета И с одним инверсным входом. В данном устройстве реализована цепочечная схема передачи сигнала опроса путем последовательного опроса, начиная со старшего разряда, и прекращения дальнейшего опроса при выявлении первой же единицы.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятый за прототип, указатель старшей единицы (Схемотехника ЭВМ. Сборник задач: учебное пособие. М.: НИЯУ МИФИ, 2012. - 240 с., рис. 53, с. 55-56), содержащий группу элементов ИЛИ объединенных в цепочку и группу элементов запрета И с одним инверсным входом.

Недостатком данных устройств является определение только одного старшего приоритета.

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

Указанный технический результат при осуществлении изобретения достигается тем, что многовыходной указатель старшей единицы содержит группу из N внешних входов запроса Z1, Z2, …, ZN (высший приоритет имеет вход ZN), К каскадов (К - количество формируемых указателей старших единиц) и К групп внешних выходов U указателей старшей единицы, при этом каждый i-й каскад (i=1, 2, …, К) содержит группу из (N-i-1) элементов ИЛИ 1_i1, 1_i2, …, 1_i(N-i-1) и группу из (N-i) элементов запрета И с одним инверсным входом 2_i1, 2_i2, …, 2_i(N-i), а также группу из (N+1-i) входов запроса в i-й каскад A_i1, A_i2, …, A_i(N+1-i) и группу из (N+1-i) внешних выходов указателей старшей единицы i-го ранга U_i1, U_i2, …, U_i(N+1-i) (1-й ранг имеет высший приоритет), каждый из первых (К-1) каскадов, кроме последнего К-го каскада, содержит также группу из (N-i) элементов И 3_i1, 3_i2, …, 3_i(N-i) и группу из (N-i) выходов запроса S_i1, S_2i, …, S_i(N-i) в следующий (i+1)-й каскад, причем внешние входы запроса Z1, Z2, …, ZN соединены с соответствующими входами запроса первого каскада A₁₁, А₁₂, …, A_1N, а в первых (К-1) каскадах, кроме последнего К-го каскада, (N-i) выходов запроса в следующий (i+1)-й каскад S_i1, S_i2, …, S_i(N-i) соединены с соответствующими (N-i) входами запроса следующего (i+1)-го каскада A_(i+1)1, A_(i+1)2, …, A_(i+1)(N-i), в каждом i-м каскаде (i=1, 2, …, К) первые (N-i) входов A_i1, A_i2, …, A_i(N-i) из группы входов запроса, кроме последнего входа запроса A_i(N-i+1), соединены со вторыми прямыми входами соответствующих элементов 2_i1, 2_i2, …, 2_i(N-i) из группы элементов запрета И с одним инверсным входом, выходы всех элементов группы из (N-i-1) элементов ИЛИ 1_i1, 1_i2, …, 1_i(N-i-1) соединены с первыми инверсными входами соответствующих первых (N-i-1) элементов 2_i1, 2_i2, …, 2_i(N-i-1) группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 2_i(N-i), у которого первый инверсный вход соединен с последним (N-i+1) входом A_i(N-i+1) группы запроса i-го каскада и первым входом последнего элемента 1_i(N-i-1) из группы элементов ИЛИ, кроме того в каждом i-м каскаде (i=1, 2, …, К) вторые входы (N-i-1) элементов 1_i1, 1_i2, …, 1_i(N-i-1) из группы элементов ИЛИ соединены с соответствующими (N-i-1) входами A_i2, A_i2, …, A_i(N-i) запроса в i-й канал, начиная со второго входа запроса, кроме последнего входа запроса A_i(N-i+1), а первые входы первых (N-i-2) элементов 1_i1, 1_i2, …, 1_i(N-i-2) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 1_i2, 1_i3, …, 1_i(N-i-1) из группы элементов ИЛИ, причем в первых (К-1) каскадах, кроме последнего К-го каскада, вторые входы (N-i) элементов 3_i1, 3_i2, …, 3_i(N-i) из группы элементов И соединены с соответствующими первыми (N-i) входами запроса в i-й канал A_i1, A_i2, …, A_i(N-i), кроме последнего входа запроса A_i(N-i+1), первые входы первых (N-i-1) элементов 3_i1, 3_i2, …, 3_i(N-i-1) из группы элементов И соединены с выходами соответствующих (N-i-1) элементов 1_i1, 1_i2, …, 1_i(N-i-1) из группы элементов ИЛИ, первый вход последнего элемента 3_i(N-i) из группы элементов И соединен с последним входом запроса A_i(N-i+1), а выходы (N-i) элементов 3_i1, 3_i2, …, 3_i(N-i) из группы элементов И в первых (К-1) каскадах, кроме последнего К-го каскада, являются группой из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад, кроме того, в каждом i-м каскаде (i=1, 2, …, К) выходы (N-i) элементов 2_i1, 2_i2, …, 2_i(N-i) из группы элементов И являются первыми (N-i) внешними выходами из группы внешних выходов указателей старшей единицы i-го ранга U_i1, U_i2, …, U_i(N-i), а последний (N-i+1) внешний выход U_i(N+1-i) соединен с последним (N-i+1) входом запроса в i-й канал A_i(N-i+1).

На фиг. 1 представлена схема предлагаемого многовыходного указателя старшей единицы для N=8 внешних входов запроса Z1, Z2, …, Z8 и К=4 групп внешних выходов U указателей старшей единицы.

На фиг. 1 введены следующие обозначения:

1_i1, 1_i2, …, 1_i(N-i-1) - группы из (N-i-1) элементов ИЛИ i-го каскада (i=1, 2, …, К);

2_i1, 2_i2, …, 2_i(N-i) - группы из (N-i) элементов запрета И с одним инверсным входом;

3_i1, 3_i2, …, 3_i(N-i) - группы из (N-i) элементов И;

Z1, Z2, …, Z8 - группа из N внешних входов запроса (высший приоритет имеет вход Z8);

A_i1, A_i2, …, A_i(N+1-i) - группы из (N+1-i) входов запроса в i-й каскад;

S_i1, S_i2, …, S_i(N-i) - группы из (N-i) выходов запроса в следующий (i+1)-й каскад;

U_i1, U_i2, …, U_i(N+1-i) - группы из (N+1-i) внешних выходов указателей старшей единицы i-го ранга (1-й ранг имеет высший приоритет).

Многовыходной указатель старшей единицы содержит группу из N внешних входов запроса Z1, Z2, …, ZN (высший приоритет имеет вход ZN), К каскадов (К - количество формируемых указателей старших единиц) и К групп внешних выходов U указателей старшей единицы (на фиг. 1 для N=8 и К=4).

Каждый i-й каскад (i=1, 2, …, К) содержит группу из (N-i-1) элементов ИЛИ 1_i1, 1_i2, …, 1_i(N-i-1) и группу из (N-i) элементов запрета И с одним инверсным входом 2_i1, 2_i2, …, 2_i(N-i), а также группу из (N+1-i) входов запроса в i-й каскад A_i1, A_i2, …, A_i(N+1-i) и группу из (N+1-i) внешних выходов указателей старшей единицы i-го ранга U_i1, U_i2, …, U_i(N+1-i) (1-й ранг имеет высший приоритет).

Каждый из первых (К-1) каскадов, кроме последнего К-го каскада содержит также группу из (N-i) элементов И 3_i1, 3_i2, …, 3_i(N-i) и группу из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад.

Внешние входы запроса Z1, Z2, …, ZN соединены с соответствующими входами запроса первого каскада А₁₁, А₁₂, …, A_1N, в первых (К-1) каскадах, кроме последнего К-го каскада, (N-i) выходов запроса в следующий (i+1)-й каскад S_i1, S_i2, …, S_i(N-i) соединены с соответствующими (N-i) входами запроса следующего (i+1)-го каскада A_(i+1)1, A_(i+1)2, …, A_(i+1)(N-i).

В каждом i-м каскаде (i=1, 2, …, К) первые (N-i) входов A_i1, A_i2, …, A_i(N-i) из группы входов запроса, кроме последнего входа запроса A_i(N-i+1), соединены со вторыми прямыми входами соответствующих элементов 2_i1, 2_i2, …, 2_i(N-i) из группы элементов запрета И с одним инверсным входом. Выходы всех элементов группы из (N-i-1) элементов ИЛИ 1_i1, 1_i2, …, 1_i(N-i-1) соединены с первыми инверсными входами соответствующих первых (N-i-1) элементов 2_i1, 2_i2, …, 2_i(N-i-1) группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 2_i(N-i), у которого первый инверсный вход соединен с последним (N-i+1) входом A_i(N-i+1) группы запроса i-го каскада и первым входом последнего элемента 1_i(N-i+1) из группы элементов ИЛИ.

Кроме того, в каждом i-м каскаде (i=1, 2, …, К) вторые входы (N-i-1) элементов 1_i1, 1_i2, …, 1_i(N-i-1) из группы элементов ИЛИ соединены с соответствующими (N-i-1) входами A_i2, A_i2, …, A_i(N-i) запроса в i-й канал, начиная со второго входа запроса, кроме последнего входа запроса A_i(N-i+1), а первые входы первых (N-i-2) элементов 1_i1, 1_i2, …, 1_i(N-i-2) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 1_i2, 1_i3, …, 1_i(N-i-1).

В первых (К-1) каскадах, кроме последнего К-го каскада, вторые входы (N-i) элементов 3_i1, 3_i2, …, 3_i(N-i) из группы элементов И соединены с соответствующими первыми (N-i) входами запроса в i-й канал A_i1, A_i2, …, A_i(N-i), кроме последнего входа запроса A_i(N-i+1). Первые входы (N-i-1) элементов 3_i1, 3_i2, …, 3_i(N-i-1) из группы элементов И соединены с выходами соответствующих (N-i-1) элементов 1_i1, 1_i2, …, 1_i(N-i-1) из группы элементов ИЛИ, а первый вход последнего элемента 3_i(N-i) из группы элементов И соединен с последним входом запроса A_i(N-i+1).

Выходы (N-i) элементов 3_i1, 3_i2, …, 3_i(N-i) из группы элементов И в первых (К-1) каскадах, кроме последнего К-го каскада, являются группой из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад.

Кроме того в каждом i-м каскаде (i=1, 2, …, К) выходы (N-i) элементов 3_i1, 3_i2, …,3_i(N-i) из группы элементов И являются первыми (N-i) внешними выходами из группы внешних выходов указателей старшей единицы i-го ранга U_i1, U_i2, …, U_i(N-i) (1-й ранг имеет высший приоритет), а последний (N-i+1) внешний выход U_i(N+1-i) соединен с последним (N-i+1) входом запроса в i-й канал A_i(N-i+1).

Принцип работы устройства состоит в следующем.

Предлагаемый многовыходной указатель старшей единицы позволяет определить среди N входов запроса Z не только сигнал с наивысшим приоритетом, но также определить сигналы со вторым, третьим, …, К-м по старшинству приоритетами. Количество требуемых К рангов приоритета определяет количество К каскадов в устройстве. Выходам U₁₁, U₁₂, …, U₁₈ указателей старшей единицы первого каскада присвоен высший приоритет (ранг). На выходах U_i указателей старшей единицы i-го каскада вырабатывается результат в виде унитарного кода «1 из N».

На входы устройства одновременно поступают сигналы запроса. При этом каждому входу запроса присваивается фиксированный приоритет. В устройстве высший приоритет присвоен входу запроса со старшим номером ZN, а далее приоритет уменьшается от номера к номеру. Младший приоритет задан у первого входа запроса Z1.

При поступлении нескольких сигналов запроса, в первом каскаде проводится поиск запроса с наибольшим приоритетом - поиск старшей (левой) единицы в группе входных запросов. На выходах U₁₁, U₁₂, …, U₁₈ указателей старшей единицы первого каскада вырабатывается результат в виде унитарного кода «1 из N» - единичный сигнал будет установлен только на одном выходе соответствующем высшему (старшему) приоритету. Количество выходов указателей старшей единицы U первого каскада равно количеству N внешних входов Z.

В первом каскаде на выходы S₁₁, S₁₂, …, S₁₇ запроса во второй каскад поступают сигналы запроса с «исключенным» запросом с высшим приоритетом. При этом во втором каскаде количество входов запроса A₁₁, А₁₂, …, А₁₇ и количество выходов указателей U уменьшаются на единицу, так как если был запрос с высшим приоритетом ZN, то он будет определен в первом каскаде. Далее на выходах U₂₁, U₂₂, …, U₂₇ устанавливается результат в унитарном коде «1 из N» для второго приоритета.

Аналогично далее формируется результат в третьем, четвертом, …, К-м каскадах.

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

На группу внешних N=8 входов запроса Z1, Z2, …, Z8 устройства поступают сигналы с установленными приоритетами. Данные сигналы поступают на входы запроса A₁₁, А₁₂, …, A₁₈ первого каскада. В первом каскаде на выходах группы элементов ИЛИ 1₁₁, 1₁₂, …, 1₁₆, объединенных в цепочку, входной код запросов преобразуется в код «00...011..1», где левая (старшая) единица соответствует высшему приоритету. Далее на выходе только одного элемента запрета И с одним инверсным входом 2₁₁, 2₁₂, …, 2₁₇, на входы которого поданы значения «01», формируется единичное значение, указывающее на запрос с высшим приоритетом, а на остальных выходах будет установлено нулевое значение. Если установлен запрос с высшим приоритетом Z8, то единичное значение устанавливается на выходе старшего указателя U₁₈. Таким образом, на выходах U₁₁, U₁₂, …, U₁₈ будет установлен унитарный код «1 из N» соответствующий запросу с наивысшим приоритетом.

Далее, так как на первые входы элементов И 3₁₁, 3₁₂, …, 3₁₇ с выходов элементов ИЛИ 1₁₁, 1₁₂, …, 1₁₈ поступает код «00...011..1», а на вторые входы - входные сигналы запроса Z1, Z2, …, Z7, кроме старшего запроса Z8, то на выходах S₁₁, S₁₂, …, S₁₇ запроса в следующий второй каскад будут установлены запросы с «исключенным» запросом с высшим приоритетом.

Далее сигналы запросов S₁₁, S₁₂, …, S₁₇ поступают на входы запроса А₂₁, А₂₂, …, А₂₇ второго каскада. На выходах элементов ИЛИ 1₂₁, 1₂₂, …, 1₂₆ формируется код «00...011..1», где левая единица соответствует второму приоритету. Затем на выходах U₂₁, U₂₂, …, U₂₇ элементов запрета И с одним инверсным входом 2₂₁, 2₂₂, …, 2₂₆ формируется унитарный код «1 из N» соответствующий второму приоритету. На выходах запроса S₂₁, S₂₂, …, S₂₆ второго канала будут установлены сигналы запросов с «исключенными» запросами первого и второго приоритетов.

Аналогично далее формируется результат в третьем, четвертом, …, К-м каскадах.

Таким образом, в предлагаемом устройстве на выходах К групп U_i1, U_i2, …, U_i(N+1-i) указателей старшей единицы будут установлены сигналы, соответствующие К рангам приоритета в унитарном коде «1 из N».

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

Многовыходной указатель старшей единицы содержит группу из N внешних входов запроса Z1, Z2, …, ZN (высший приоритет имеет вход ZN), K каскадов (K - количество формируемых указателей старших единиц) и K групп внешних выходов U указателей старшей единицы, при этом каждый i-й каскад (i=1, 2, …, K) содержит группу из (N-i-1) элементов ИЛИ 1_i1, 1_i2, …, 1_i(N-i-1) и группу из (N-i) элементов запрета И с одним инверсным входом 2_i1, 2_i2, …, 2_i(N-i), а также группу из (N+1-i) входов запроса в i-й каскад A_i1, A_i2, …, A_i(N+1-i) и группу из (N+1-i) внешних выходов указателей старшей единицы i-го ранга U_i1, U_i2, …, U_i(N+1-i) (1-й ранг имеет высший приоритет), каждый из первых (K-1) каскадов, кроме последнего K-го каскада, содержит также группу из (N-i) элементов И 3_i1, 3_i2, …, 3_i(N-i) и группу из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад, причем внешние входы запроса Z1, Z2, …, ZN соединены с соответствующими входами запроса первого каскада A₁₁, А₁₂, …, A_1N, а в первых (K-1) каскадах, кроме последнего K-го каскада, (N-i) выходов запроса в следующий (i+1)-й каскад S_i1, S_i2, …, S_i(N-i) соединены с соответствующими (N-i) входами запроса следующего (i+1)-го каскада A_(i+1)1, A_(i+1)2, …, A_(i+1)(N-i), в каждом i-м каскаде (i=1, 2, …, K) первые (N-i) входов A_i1, A_i2, …, A_i(N-i) из группы входов запроса, кроме последнего входа запроса A_i(N-i+1), соединены со вторыми прямыми входами соответствующих элементов 2_i1, 2_i2, …, 2_i(N-i) из группы элементов запрета И с одним инверсным входом, выходы всех элементов группы из (N-i-1) элементов ИЛИ 1_i1, 1_i2, …, 1_i(N-i-1) соединены с первыми инверсными входами соответствующих первых (N-i-1) элементов 2_i1, 2_i2, …, 2_i(N-i-1) группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 2_i(N-i), у которого первый инверсный вход соединен с последним (N-i+1) входом A_i(N-i+1) группы запроса i-го каскада и первым входом последнего элемента 1_i(N-i-1) из группы элементов ИЛИ, кроме того, в каждом i-м каскаде (i=1, 2, …, K) вторые входы (N-i-1) элементов 1_i1, 1_i2, …, 1_i(N-i-1) из группы элементов ИЛИ соединены с соответствующими (N-i-1) входами A_i2, A_i2, …, A_i(N-i) запроса в i-й канал, начиная со второго входа запроса, кроме последнего входа запроса A_i(N-i+1), а первые входы первых (N-i-2) элементов 1_i1, 1_i2, …, 1_i(N-i-2) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 1_i2, 1_i3, …, 1_i(N-i-1) из группы элементов ИЛИ, причем в первых (K-1) каскадах, кроме последнего K-го каскада, вторые входы (N-i) элементов 3_i1, 3_i2, …, 3_i(N-i) из группы элементов И соединены с соответствующими первыми (N-i) входами запроса в i-й канал A_i1, A_i2, …, A_i(N-i), кроме последнего входа запроса A_i(N-i+1), первые входы первых (N-i-1) элементов 3_i1, 3_i2, …, 3_i(N-i-1) из группы элементов И соединены с выходами соответствующих (N-i-1) элементов 1_i1, 1_i2, …, 1_i(N-i-1) из группы элементов ИЛИ, первый вход последнего элемента 3_i(N-i) из группы элементов И соединен с последним входом запроса A_i(N-i+1), а выходы (N-i) элементов 3_i1, 3_i2, …, 3_i(N-i) из группы элементов И в первых (K-1) каскадах, кроме последнего K-го каскада, являются группой из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад, кроме того, в каждом i-м каскаде (i=1, 2, …, K) выходы (N-i) элементов 2_i1, 2_i2, …, 2_i(N-i) из группы элементов И являются первыми (N-i) внешними выходами из группы внешних выходов указателей старшей единицы i-го ранга U_i1, U_i2, …, U_i(N-i), а последний (N-i+1) внешний выход U_i(N+1-i) соединен с последним (N-i+1) входом запроса в i-й канал A_i(N-i+1).