УСТРОЙСТВО СОРТИРОВКИ

Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах цифровой обработки изображений.
В частности, предлагаемое устройство можно использовать, например, для медианной фильтрации изображений с целью подавления шума.
Известно «Устройство для обработки изображений объектов, авторы В.В. Грицык, А.Ю. Луцык и P.M. Паленичка, описанное в патенте SU 1226500 кл. G 06 К 9/36, опубликованное в 1986 году, в котором используется алгоритм параллельной обменной сортировки, основанный на попарной параллельной перестановке чисел сортируемой последовательности. Для этого служат компараторы, каждый из которых имеет два информационных входа, управляющий вход и два информационных выхода, и элеп/1енты задержки, каждый из которых имеет один вход и один выход. При этом предложенное устройство реализует метод «пузырьковой сортировки и для девяти элементов выполняет свои функции с задержкой равной девяти. В предлагаемом устройстве путем изменения процесса сортировки время задержки сокращается до семи. Данная система является наиболее близким аналогом предлагаемой.
В заявке Л.В. Петрова, М.В. Гукасовой и Г.В. Сакварелидзе «Устройство обработки изображений, опубликованной в 1991 году №1621058 кл. G06 К 9/36, и являющейся продолжением вышеописанной заявки, с целью упрощения устройства из блока сортировки исключаются компараторы и элементы задержки, а выполнение функции обеспечивается введением блоков памяти, выполненных в виде ПЗУ. Данный подход не обеспечивает увеличения быстродействия сортировки, т.е. предлагаемого технического результата.
Цель изобретения - повышение быстродействия устройства.
На фиг.1 представлена схема конкретной реализации предлагаемого устройства; на фиг.2 - вариант представления устройства сетью сортировки.
Устройство содержит входы 1-10, управляющий вход 11, первую группу последовательно соединенных элементов задержки 12, первую группу параллельно соединенных компараторов 13, вторую группу параллельно соединенных компараторов 14, третью группу параллельно соединенных компараторов 15, четвертую группу параллельно соединенных компараторов 16, пятую группу параллельно соединенных компараторов 17, шестую группу
параллельно соединенных компараторов 18, седьмую группу параллельно соединенных компараторов 19; вторую группу элементов задержки 20, третью группу элементов задержки 21; четвертую группу элементов задержки 22.
Устройство работает следующим образом.
Устройство осуществляет параллельно-последовательную сортировку входной последовательности двоичных чисел, например, элементов изображения.
Исходная последовательность подается на входы 1-10. Если требуется отсортировать число элементов меньше десяти, то на соответствующие входы 110 подается нулевой потенциал.
На управляющий вход 11 поступает сигнал установки групп компараторов 13-19 в начальное состояние перед сравнением каждой новой пары чисел. Этот сигнал может быть выработан, например, компаратором, который осуществляет сравнение кода количества тактовых импульсов и кода количества разрядов элементов входного изображения для подачи кодов элементов сортируемой последовательности на входы 1-10. Время задержки элемента задержки 12 равно времени задержки элементов задержки 20-22, которое в свою очередь определяется временем задержки компараторов 13-19.
Для доказательства работоспособности устройства сортировки его схематично можно представить в виде сети сортировки показанной на фиг.2. В этой сети числа поступают слева, а компараторные модули изображены вертикальными соединениями между двумя прямыми. Существует теорема, с помощью которой можно доказать, что предлагаемое устройство полностью выполняет возложенную на него функцию сортировки.
Теорема. Если сеть с п входами сортирует в неубывающем порядке все 2 последовательностей из нулей и единиц, то она будет сортировать в неубывающем порядке любую последовательность п чисел.
Доказательство. Если /jfxj -любая монотонная функция, для которой f(x)(y) при , и если данная сеть преобразует {Xi,...,Xn} в {у-1,...,Уп} , то как не трудно видеть, эта сеть преобразует {f(xi),...,f(Xn)} в {1(у),...,1(у„)} . Если  при некотором / , то рассмотрим монотонную функцию f, которая для всех чисел у/ принимает значение О, а для всех чисел у, - значение 1. Эта функция определяет последовательность нулей и единиц {f(x),...,f(Xn)}, которая не сортируется данной
сетью. Следовательно, если все последовательности нулей и единиц поддаются сортировке, то будем иметь  для всех 1 л . Что и требовалось доказать.
Из теоремы следует, что если на сеть, представленную на фиг.2, будут поступать двоичные коды чисел от О до 2 -1 (в нашем случае ), то легко убедится, что все 1024 последовательности будут отсортированы. Следовательно, возможна сортировка любой последовательности десяти чисел.