Patent ID: 6021131
Filing Date: 2000-02-01
Classification: H04L,H04Q

Abstract:
A sorting network B.sub.n, comprising:network inputs for receiving a vector of 2.sup.n input signals representing corresponding values;network outputs for providing 2.sup.n sorted signals representing the 2.sup.n input signals sorted according to their values;a plurality of comparison circuits, wherein:each said comparison circuit has two inputs and two outputs;each said comparison circuit has a network depth, said network depths having an order from minimum to maximum;said circuit plurality is arranged in grid columns by network depth;network inputs are connected to circuits having minimum network depth;the two outputs of each said comparison circuit are connected to the inputs of comparison circuits having greater network depth, if there are any;comparison circuits having maximum network depth are connected to the network outputs;the comparison circuits are arranged in functional groupings including sorters and mergers, wherein:said functional groupings are arranged in a manner defined by a recursive structure of the sorting network;mergers having comparison circuits of similar network depth are stacked in identical grid columns that include 1/4(2.sup.n) mergers of a kind that comprises four comparison circuits, said mergers to be referred to as M.sub.2 mergers, and further wherein:each merger M.sub.2 is laid out using five grid rows.