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

Реферат

 

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

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

Известно устройство для вычисления порядковых статистик, содержащее N регистров (N - количество чисел), N - элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, N компараторов, блок постоянной памяти, регистры выполнены сдвиговыми, при этом последовательный выход i-го регистра сдвига (i= ) подключен к i-ому адресному входу блока постоянной памяти, к первому входу i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и к первому информационному входу i-го коммутатора, второй информационный вход которого соединен с выходом соответствующего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых подключены к выходу блока постоянной памяти и являются выходом устройства, вход считывания блока постоянной памяти объединен с управляющими входами коммутаторов и является первым тактовым входом устройства, входы сдвига сдвиговых регистров объединены и являются вторым тактовым входом устройства.

Устройство реализует вычисление значения заданной порядковой статистики последовательности чисел путем последовательного анализа значений соответствующих разрядов всех этих чисел. Определение значения заданной порядковой статистики для множества из N М-разрядных чисел осуществляется за (N+M) тактов работы.

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

Известно устройство для вычисления порядковых статистик, содержащее (N-2) групп запоминающих элементов, N последовательно соединенных элементов задержки, выход первого элемента задержки подключен к первым входам (N-1) компараторов первой группы, второй вход k-го компаратора (k = ) первой группы соединен с входом (k+1)-го элемента задержки, входы i-х запоминающих элементов i-й группы (i = ) соединены с выходами первого по i-й запоминающих элементов (i+1)-й группы (где i = ), входы запоминающих элементов (N-2)-й группы подключены к выходам "Меньше" (N-2) компараторов первой группы, входы блоков постоянной памяти первой группы соединены с выходами "Больше" компараторов первой группы и запоминающих элементов всех групп, выходы элементов задержки подключены к информационным входам мультиплексора, выход которого является выходом устройства, N блоков постоянной памяти второй группы, N компараторов второй группы, регистр ранга и преобразователь кода, состоящий из шифратора приоритета и дешифратора, при этом выходы шифратора приоритета подключены к соответствующим входам дешифратора, выход которого соединен с управляющим входом мультиплексора, входы блоков постоянной памяти второй группы соединены с соответствующими выходами компараторов второй группы и запоминающих элементов всех групп, информационный выход j-го блока постоянной памяти первой группы подключен к первому входу j-го компаратора (j = ) второй группы, информационный выход j-го блока постоянной памяти второй группы соединен со вторым входом j-го компаратора второй группы, третий вход которого соединен с выходом регистра ранга, выходы компараторов второй группы соединены с соответствующими входами шифратора приоритета.

Устройство реализует вычисление результатов операции ранговой фильтрации, т. е. значения заданной локальной порядковой статистики по скользящей апертуре (скользящему окошку) длины N. Для этого значение текущего отсчета сигнала сравнивается со значениями остальных отсчетов текущей апертуры и результаты сравнения запоминаются. На основании полученных таким образом и сохраненных полученных ранее результатов сравнения значений соответствующих отсчетов сигнала для каждого отсчета xi текущей апертуры определяется количество а и b отсчетов той же апертуры, значения которых больше и меньше значения данного отсчета xi.На основании полученных таким образом значений а и b определяется положение в апертуре отсчета, имеющего заданный ранг, и его значение коммутируется на выход устройства. Таким образом, в каждом такте работы устройства на его выходе формируется значение заданной локальной порядковой статистики для данной текущей апертуры.

Операция вычисления значений локальных порядковых статистик широко используется при обработке различного рода сигналов, в частности, при обработке телевизионных изображений (Ярославский Л.П., Цифровая обработка сигналов в оптике и голографии: Введение в цифровую оптику. - М. Радио и связь, 1987, с. 214-241). Причем, как правило, необходимо иметь значения всех локальных порядковых статистик для текущей апертуры, т.е. вариационный ряд значений отсчетов текущей апертуры (упорядоченную в порядке возрастания (убывания) последовательность значений отсчетов текущей апертуры).

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

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

Цель изобретения - расширение области применения.

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

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

Суперпозиция этих двух операций описывает способ рекуpрентного формирования вариационного ряда значений элементов скользящей апертуры. Рекуpрентное формирование вариационного ряда значений элементов скользящей апертуры позволяет существенно снизить уровень вычислительных (аппаратных) затрат и осуществить параллельное формирование за один такт работы значений всех элементов искомого вариационного ряда.

Цель достигается тем, что в устройство для вычисления локальных порядковых статистик, содержащее N последовательно соединенных элементов задержки, (N-1) компараторов, группу из (N-1) запоминающих элементов, первый и второй блоки постоянной памяти, группу из N блоков постоянной памяти и первый мультиплексор, причем выход первого элемента задержки подключен к первым входам компараторов, второй вход k-го компаратора (k = ) соединен с выходом (k+1)-го элемента задержки, введены группа из N мультиплексоров, группа из N регистров, причем блоки постоянной памяти группы, мультиплексоры группы и регистры группы объединены в N блоков коммутации, каждый из которых содержит блок постоянной памяти, мультиплексор и регистр, причем в каждом блоке коммутации его первый и второй управляющие входы соединены с соответствующими входами блока постоянной памяти данного блока коммутации, выход которого соединен с управляющими входами мультиплексора данного блока коммутации, первый - четвертый входы этого мультиплексора соединены соответственно с первым - третьим входами блока коммутации и выходом регистра данного блока коммутации, выход мультиплексора данного блока коммутации соединен со входом данного блока коммутации, выход которого является выходом блока коммутации, выходы "Больше" компараторов соединены со входами первого блока постоянной памяти, выход которого соединен с первыми управляющими входами блоков коммутации, выходы "Меньше-равно" компараторов соединены с входами соответствующих запоминающих элементов группы, выходы которых соединены с входами второго блока постоянной памяти, выход которого соединен со вторыми управляющими входами блоков коммутации, выход предшествующего блока коммутации соединен с первым входом последующего блока коммутации, выход которого соединен с третьим входом предшествующего блока коммутации, вторые входы блоков коммутации объединены и соединены с выходом первого элемента задеpжки, первый вход первого блока коммутации и третий вход N-го блока коммутации соединены со входами нулевого и единичного кода устройства соответственно, выход i-го блока коммутации (i = ) соединен с выходом значения i-й локальной порядковой статистики устройства и с i-м входом первого мультиплексора, управляющий вход которого соединен со входом заданий ранга устройства, а выход - с выходом значения заданной локальной порядковой статистики устройства, тактовые входы элементов задержки, регистров и запоминающих элементов объединены и соединены с тактовым входом устройства.

Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается наличием новых блоков, а также их связями между собой и с остальными элементами схемы. Таким образом, заявляемое устройство соответствует критерию "Новизна".

Сопоставительный анализ с другими техническими решениями показывает, что мультиплексоры, компараторы и блоки постоянной памяти широко известны (см. например, Справочник по устройствам цифровой обработки информации - К. , Техника, 1988). Блок из N элементов задержки может быть реализован как последовательное соединение N элементов задержки на один такт работы. В качестве элемента задержки на один такт работы может быть использован параллельный регистр на MS (двойных) триггерах. Двойной триггер представляет собой последовательное соединение двух триггеров, один из которых срабатывает по переднему фронту тактового импульса, а другой - по заднему фронту. В параллельном регистре на MS-триггерах сначала осуществляется прием нового значения со входа регистра и лишь потом осуществляется формирование нового записанного значения (сдвиг) на выходе регистра. Реализовать k-разрядный блок элементов задержки длины N можно также при помощи параллельного соединения k сдвиговых регистров длины N на MS-триггерах. Тактовый подход к реализации блоков элементов задержки широко известен (Справочник по устройствам цифровой обработки информации/-К. , Техника, 1988, с. 337, рис. 5.48). Параллельные регистры и сдвиговые регистры на MS-триггерах широко известны (Справочник по устройствам цифровой обработки информации/-К., Техника, 1988, с. 54-56). Регистры группы реализуются как параллельные регистры на MS-триггерах, которые как указывалось ранее, широко известны. Запоминающие элементы группы реализуются как сдвиговые регистры на MS-триггерах, которые также широко известны. При этом k-й запоминающий элемент (k = ) реализуется как сдвиговый регистр длины k.

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

Это позволяет сделать вывод о соответствии решения критерию "Существенные отличия".

На фиг. 1 представлена схема заявляемого устройства; на фиг.2,а - взаимное расположение элементов текущей апертуры i и предшествующей апертуры i - 1 ; б - положение удаляемого элемента Y (заштриховано) вариационного ряда апертуры i - 1 и сдвигаемых на одну позицию влево элементов того же ряда; в - взаимное положение вводимого элемента Z апертуры i и сдвигаемых на одну позицию вправо элементов полученной на первом этапе упорядоченной последовательности (элементы последовательности, значения которых меньше значения Z, заштрихованы).

Устройство содержит N элементов 1.1, 1.2,...1.N задержки, группу 2 из (N-1) компараторов 3.1, 3.2,...,3.N-1, регистр, состоящий из группы из ( - 1) запоминающих элементов 4.1, 4.2,...,4.N-1, блоки 5 и 6 постоянной памяти, мультиплексор 7, N блоков 8.1, 8.2,...,8.N коммутации, причем блок 8. j коммутации (j = ) содержит блок 9.j постоянной памяти, мультиплексор 10. j, регистр 11.j, информационный вход 12 устройства, вход 13 задание ранга устройства, тактовый вход 14 устройства, выходы 15.1, 15.2,...,15.N значений соответствующих локальных порядковых статистик устройства, выход 16 заданной локальной порядковой статистики устройства.

Элементы 1.1, 1.2,...1.N задержки соединены последовательно. Информационный вход 12 устройства соединен со входом элемента 1.1 задержки. Выход элемента 1.1 задержки соединен с первыми входами компараторов 3.1, 3.2,..., 3.N-1 и вторыми входами блоков 8.1, 8.2,...,8.N коммутации.

Выход элемента 1.k+1(k = ) соединен со вторым входом компаратора 3. k. Выход больше компаратора 3.k(k = ) соединен с k-м входом блока 5 постоянной памяти. Выход блока 5 постоянной памяти соединен с первыми управляющими входами блоков 8.1, 8.2,....,8.N коммутации. Выход "Меньше-равно" компаратора 3.k(k = ) соединен с входом запоминающего элемента 4. Выход запоминающего элемента 4.k соединен с k-м входом блока 6 постоянной памяти. Выход блока 6 постоянной памяти соединен со вторыми управляющими входами блоков 8.1, 8.2, ...,8.N коммутации. Первый и второй управляющие входы блока 8. j коммутации (j = ) соединены со входами блока 9.j постоянной памяти. Выход блока 9.j постоянной памяти соединен с управляющим входом мультиплексора 10. j. Выход мультиплексора 10.j соединен со входом регистра 11.j. Выход регистра 11.j соединен с выходом блока 8.j коммутации и четвертым входом мультиплексора 11.j. Первый-третий вход мультиплексора 10.j соединены с первым-третьим входами блока 8.j коммутации.

Выход блока 8.m коммутации (m = ) соединен с первым входом блока 8.m + 1 коммутации, выход блока 8.m + 1 соединен с третьим входом блока 8.m коммутации. Первый вход блока 8.1 коммутации и третий вход блока 8.N коммутации соединены со входами нулевого и единичного кода устройства соответственно. Выход блока 8. j коммутации (j = ) соединен с j-м входом мультиплексора 7 и выходом 15.j значения j-й порядковой статистики устройства. Вход 13 задания ранга устройства соединен с управляющим входом мультиплексора 7. Выход мультиплексора 7 соединен с выходом 16 значения заданной порядковой статистики устройства.

Тактовые входы элементов 1.1, 1.2,...,1.N задержки, запоминающих элементов 4.1, 4.2,...,4.N-1, регистров 11.1, 11.2,...,11.N объединены и соединены с тактовым входом 14 устройства.

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

Предлагаемое устройство реализует метод рекуpрентного формирования значений элементов текущей локальной окрестности. Суть метода заключается в следующем.

Текущая апертура i длины N( i = {xj} j = } и предшествующая апертура i - 1 той же длины (см. фиг.2а) отличаются друг от друга двумя элементами: элементом Y= xi-N, который "уходит" и элементом Z = xi, вновь "пришедшим".

Допустим, что мы имеет вариационный ряд {ai } i = (упорядоченную в порядке возрастания последовательность) значений элементов предшествующей апертуры i - 1 . Для того, чтобы сформировать вариационный ряд {cj} j = значений элементов текущей апертуры i , необходимо из вариационного ряда { aj} j = предшествующей апертуры i - 1 удалить значение Y (заштриховано), а все элементы вариационного ряда, находящиеся "справа", сдвинуть на одну позицию влево (см. фиг.2,б). Затем для полученной таким образом последовательности {bj} j = определяются ее элементы, имеющие значения меньше (фиг.2,b, заштрихованы). Значение Z "вставляется" сразу за этими элементами, а остальные элементы последовательности {bj} сдвигаются на одну позицию вправо (см. фиг.2,б). Выполнив эти две операции, получим значение элементов вариационного ряда {cj} j = текущей апертуры i .

Таким образом, суть метода сводится к следующему.

Обозначим через d ранг элемента Y относительно выборки значений элементов апертуры i - 1 ,l через е - ранг элемента Z относительно выборки значений элементов апертуры i . Иначе говоря, d - это количество элементов апертуры i - 1 , значение которых меньше значения Y , а l - количество элементов апертуры i , значение которых меньше значения Z.

d = h(xj,Y) (1) l = (2) h(xj,Z)= (3) Операция удаления из вариационного ряда {aj} значения, равного Y , и сдвиг соответствующих элементов "влево" описывается выражением bк= (4) Операция "вставки" в последовательность {bk}, k = значения Z и сдвиг вправо соответствующих элементов последовательности описывается выражением: Cj= (5) Суперпозиция (4) и (5) дает следующую зависимость: Ci= Выражение (6)-(10) описывает алгоритм рекуpрентного формирования значений элементов вариационного ряда {cj} текущей апертуры i на основе вариационного ряда {aj} предшествующей апертуры i - 1 .

Рассмотрим следующий пример.

Допустим, что в предшествующий момент времени имеем апертуру i - 1: i - 1 : 52146 и ее вариационный ряд: {aj}, j = : 12456 В текущий момент времени имеем апертуру i : i : 21463 Тогда Y = 5 (уходящий элемент), Z = 3 (вновь пришедший элемент).

При этом d = rang (5) = 3 e = rang (3) = 2 Тогда согласно (6) - (10): c1 = a1 = 1 (согласно (6)) с1 = а2 = 2 (согласно (6)) с3 = Z = 3 (согласно (8)) с4 = а3 = 4 (согласно (9)) с5 = а5 = 6 (согласно (10)).

Таким образом мы имеем вариационный ряд {cj}j = ,значений элементов текущей апертуры i : {cj} j = :12346 Отсчеты входного сигнала (двоичные числа) последовательно поступают на вход 12 устройства и в каждом такте работы устройства на соответствующих выходах элементов 1.1, 1.2,...,1.N задержки присутствуют коды N последних последовательных отсчетов сигнала, т.е. формируются значения элементов текущей выборки. Пусть в текущем i-м такте работы на выходах элементов 1.1, 1.2, . ..,1.N задержки сформировались коды отсчетов текущей i-й апертуры i длины N.

i = {xj} j = Значение отсчета xi с выхода элемента 1.1 задержки поступает на третьи входы блоков 8.1, 8.2,...,8.N коммутации и первые входы компараторов 3.1, 3.2, . . .,3.N-1. Значение отсчета xi-k(k = ) поступает на второй вход компаратора 3.k. Компараторы 3.1, 3.2,...,3.N-1 имеют два выхода: "Больше" и "Меньше - равно". Результаты сравнения значения отсчета xi со значениями отсчетов xi-1,...,xi-N+1 с выходов "Больше" компараторов 3.1, 3.2,...,3.N-1 поступают на соответствующие входы блока 5 постоянной памяти.

Результаты сравнения значения отсчета xi и xi-2,...,xi-N+1 с выходов "Меньше - равно" компараторов 3.1, 3.2,...,3.N-1 поступают соответственно на входы запоминающих элементов 4.1, 4.2,...,4.N-1. Запоминающий элемент 4. k(k = ) осуществляет последовательное запоминание результатов сравнения соответствующих отсчетов сигнала. При этом запоминающий элемент 4.k(k = ) имеет одноразрядный вход и длину (N-k). В текущем i-м такте работы на выходе запоминающего элемента 4. k формируется результат сравнения "Меньше-равно" значений отсчетов xi-N+kи xi-N. Признаки сравнения значений отсчетов xi-1, xi-2,...,xi-N+1 и значение отсчета xi-N поступают на соответствующие входы блока 6 постоянной памяти. В блоках 5 и 6 постоянной памяти реализуется табличное вычисление результатов функции суммирования соответствующих результатов сравнения, поступающих на их соответствующие входы.

Тогда в i-м такте работы на выходе блока 5 постоянной памяти будет формироваться значение l, равное количеству элементов текущей апертуры i , значение которых меньше значения отсчета xi, а на выходе блока 6 постоянной памяти - значение d, равное количеству элементов предшествующей апертуры i - 1 , значение которых меньше значения отсчета xi-N. Значения величин l и d с выходов блоков 5 и 6 постоянной памяти поступают на первый и второй управляющие входы блоков 8.1, 8.2,...,8.N коммутации, на третьи входы которых поступает значение Z = xi с выхода элемента 1.1 задержки. Параллельно в i-м такте работы значение aj(j = ) j-го элемента вариационного ряда значений элементов предшествующей апертуры i - 1 с выхода регистра 11.j блока 8.j коммутации поступает на четвертый вход мультиплексора 10.j блока 8.j и на его выход. Значение с выхода предшествующего блока 8.k(k = ) коммутации поступает на первый вход последующего блока 8.k+1 коммутации, а значение с его выхода - на третий вход предшествующего блока 8.k коммутации. Таким образом, на соответствующих входах мультиплексора 10.j блока 8.j(j = ) коммутации формируются значения величин аj-1, xi, aj+1, aj, (где ао = 0, aN+1 = M, где M = 2 -1 , - количество разрядов на входе 12 устройства).

В блоке 9. j постоянной памяти блока 8.j коммутации, на входы которого поступают значения l и d с первого и второго управляющего входов блока 8.j коммутации, реализовано согласно (6) - (10) табличное вычисление номера входа мультиплексора 10.j, который необходимо подключить к его выходу, чтобы получить на нем значение cj j-го элемента вариационного ряда текущей апертуры i . Значение cj с выхода мультиплексора 10.j поступает на вход соответствующего регистра 11.j блока 8.j коммутации. Таким образом, в каждом такте работы на входах соответствующих регистров 11.1, 11.2,...,11.N блоков 8.1, 8.2,...,8.N коммутации параллельно формируются значения С1, С2, ...,СN элементов вариационного ряда текущей апертуры i В начальный момент времени элементы 1.1, 1.2,...,1.N задержки и регистры 11.1, 11.2,...,11.N в блоках 8.1, 8.2,...,8.N коммутации обнулены, а запоминающие элементы 4.1, 4.2,...,4.N-1 установлены в единичное состояние. Такая начальная установка эквивалента обработки последовательности нулевых значений. Затем на протяжении и первых N тактов работы происходит последовательное формирование значений элементов первой апертуры 1= {xj}, j = и параллельно рекуpрентно формируется вариационный ряд значений соответствующей апертуры (последовательно из построенного ранее вариационного ряда удаляется нулевое значение и соответствующим образом вводится значение соответствующего отсчета апертуры 1 ). В последующих тактах работы, начиная с (N + +1)-го, имеем в регистрах 11.1, 11.2,...,11.N значение элементов вариационного ряда соответствующей текущей апертуры.

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

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

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЛОКАЛЬНЫХ ПОРЯДКОВЫХ СТАТИСТИК, содержащее регистр, два сумматора, группу компараторов и группу элементов задержки, информационный вход первого из которых является информационным входом устройства, тактовый вход которого подключен к тактовым входам элементов задержки группы, выход i-го элемента задержки группы (где i = 1, (n - 1), n - число элементов задержки) соединен с информационным входом i + 1-го элемента задержки группы, выход первого элемента задержки группы подключен к первым входам компараторов группы, выход j-го элемента задержки группы (где j= ) соединен с вторым входом j - 1-го компаратора группы, выходы "Больше" компараторов группы подключены к входам первого сумматора, отличающееся тем, что, с целью расширения области применения, в него введены мультиплексор и каналы обработки информации, каждый из которых состоит из мультиплексора, регистра и блока постоянной памяти, причем выходы "Меньше" или "Равно" компараторов группы соединены с разрядным информационным входом регистра, разрядный выход которого подключен к входам второго сумматора, выходы первого и второго сумматоров соединены соответственно с первыми и вторыми адресными входами блоков постоянной памяти каналов обработки информации, в каждом канале обработки информации выход блока постоянной памяти соединен с первым управляющим входом мультиплексора, выход которого подключен к информационному входу регистра, тактовые входы регистра и регистров каналов обработки информации соединены с тактовым входом устройства, выход первого элемента задержки группы подключен к первым информационным входам мультиплексоров каналов обработки информации, второй информационный вход мультиплексора первого канала обработки информации является входом задания нулевого сигнала устройства, выход регистра i-го канала обработки информации подключен к второму информационному входу мультиплексора i + 1-го канала обработки информации, выход регистра j-го канала обработки информации соединен с третьим информационным входом мультиплексора j - 1-го канала обработки информации, третий информационный вход мультиплексора n-го канала обработки информации соединен с входом задания единичного сигнала устройства, выходы регистров каналов обработки информации подключены к информационным входам мультиплексора, управляющий вход и выход которого являются соответственно входом задания ранга и выходом устройства, выход регистра K-го канала обработки информации (K=) соединен с четвертым информационным входом мультиплексора K-го канала обработки информации.

РИСУНКИ

Рисунок 1, Рисунок 2