KR100194588B1

KR100194588B1 - Sorting method using bitmap and sorting device

Info

Publication number: KR100194588B1
Application number: KR1019960035749A
Authority: KR
Inventors: 전병윤; 전용일; 이명호; 박권철
Original assignee: 이계철; 한국전기통신공사; 정선종; 한국전자통신연구원
Priority date: 1996-08-27
Filing date: 1996-08-27
Publication date: 1999-06-15
Anticipated expiration: 2016-08-27
Also published as: KR19980016217A

Abstract

본 발명은 비트맵으로 표현된 비교치들을 정렬하여 그들 중에서 최대치 또는 최소치를 구하는 비트맵을 이용한 정렬방법 및 그 정렬장치에 관한 것이다. 본 발명은 보다 간단한 알고리듬으로 정렬하여 정렬시간을 단축하며, 하드웨어로 구현될 때에도 조합회로로 구성하여 단일 클럭 주기 내에서 동작함으로써 정렬시간을 더욱 단축하는 데에 그 목적이 있다. 본 발명의 하드웨어 구성은 어레이 배타적 논리합 수단과, 열별배치 수단과, 최대ㆍ최소 검색회로과, 행별배치 수단과, 어레이 논리합 수단으로 구성된다.The present invention relates to a sorting method using a bitmap and to a sorting apparatus for sorting the comparison values represented by the bitmap to obtain the maximum or minimum among them. The present invention aims to shorten the alignment time by aligning with a simpler algorithm, and to shorten the alignment time by operating in a single clock cycle by configuring a combination circuit even when implemented in hardware. The hardware configuration of the present invention is composed of array exclusive OR means, column order arrangement means, maximum and minimum search circuits, row placement means and array OR means.

Description

Sorting method using bitmap and sorting device

본 발명은 비트맵을 이용한 정렬방법 치 그 정렬장치에 관한 것으로서, 특히 비트맵으로 표현된 비교치들을 정렬하여 그들 중에서 최대치 또는 최소치를 구하는 비트맵을 이용한 정렬방법 및 그 정렬장치에 관한 것이다.BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a sorting device using a bitmap, and more particularly, to a sorting method using a bitmap and a sorting device using a bitmap for arranging comparison values expressed in a bitmap to obtain a maximum value or a minimum value among them.

일반적으로, 정렬 알고리즘은 네트워크로 구성하는 경우가 많다.In general, the sorting algorithm is often configured as a network.

네트워크로 구성되어 있는 시스템에서 정렬할 때에는 다수 개의 클럭을 사용하여 비교치 등을 정렬한다.When sorting in a networked system, multiple clocks are used to sort the comparisons.

배처 소팅 네트워크(bather's sorting network)는 다단계의 바이토닉 소팅 네트워크(bitonic sorting network)로 이루어져 있다.The batcher's sorting network consists of a multi-stage bitonic sorting network.

바이토닉 소팅 네트워크는 직렬 비교기, 레지스터 및 2:1 MUX를 기본요소로 하여 다단계의 요소로 구성되기 때문에 다수 개의 클럭이 비교치 정렬에 소요된다.A bitonic sorting network consists of a series of elements, with serial comparators, registers, and 2: 1 MUX as the basic elements, so multiple clocks are needed for comparison ordering.

일례로, 16×16의 멀티 병렬버퍼 구조의 스위치에서 입력 패킷들을 최소크기의 버퍼에 차례로 입력시키는 기능을 구현하는 예를 들 수 있다.For example, an example of implementing a function of sequentially inputting input packets into a buffer having a minimum size in a switch of a 16 × 16 multi-parallel buffer structure.

그 경우에 종래의 정렬방법 및 정렬장치는 16개의 버퍼 크기를 비교하기 위해 최소한 4(=log₂16)개의 클럭이 소요되며 16개의 입력단에 들어온 패킷을 처리하기 위해 64클럭(16개×4클럭/개)이 필요하게 된다.In that case, the conventional sorting method and sorting device requires at least 4 (= log ₂ 16) clocks to compare the 16 buffer sizes and 64 clocks (16 × 4 clocks) to process packets coming in at 16 inputs. /) Will be required.

이 스위치의 구현에서 사용되는 전체 클럭의 갯수가 제한되는 경우에는 입력패킷을 병렬 버퍼에 입력하는 데에 미처 64개의 클럭을 할당하지 못하게 되어 종래의 정렬방법 및 정렬장치를 적용한 멀티버퍼 병렬 스위치를 구현할 수 없게 된다.If the total number of clocks used in the implementation of this switch is limited, 64 clocks cannot be allocated to input the input packets into the parallel buffers, thereby implementing a multibuffered parallel switch employing a conventional alignment method and alignment device. It becomes impossible.

종래의 정렬방법 및 정렬장치에서는 비교치들의 최대치나 최소치를 구하기 위해 다수 개의 클럭을 사용하기 때문에 정렬에 할당되는 클럭의 갯수에 제한이 있을 때에 종래의 정렬방법 및 정렬장치를 사용하는 것은 상당한 부담이 되거나 적용하기에 불가능한 경우도 있다는 문제점이 있었다.Since a conventional sorting method and sorting apparatus uses a plurality of clocks to obtain the maximum or minimum value of the comparison values, using the conventional sorting method and sorting apparatus is a significant burden when the number of clocks allocated to the sorting is limited. There was a problem that there are cases where it is impossible or impossible to apply.

상기 문제점을 해결하기 위한 본 발명은 보다 간단한 알고리듬으로 정렬하여 정렬시간을 단축하며, 하드웨어로 구현될 때에도 조합회로로 구성하여 단일 클럭 주기 내에서 동작함으로써 정렬시간을 단축하는 데에 그 목적이 있다.The present invention for solving the above problems is to shorten the alignment time by alignment with a simpler algorithm, and to reduce the alignment time by operating in a single clock cycle by configuring a combination circuit even when implemented in hardware.

제1a도는 비교대상들의 형식을 표시한 비트맵을 나타낸 도면.1A is a diagram showing a bitmap indicating the format of comparison objects.

제1b도는 비교대상들의 4개의 비트맵의 예를 나타낸 도면.1B is a diagram showing an example of four bitmaps of comparison objects.

제1c도는 비교대상들을 인접한 비트끼리 XORing한 결과를 나타낸 도면.Figure 1c is a view showing the result of XORing the adjacent bits of the comparison targets.

제2도는 비교대상들 중에서 최소치를 구하는 순서도.2 is a flowchart for obtaining a minimum value among the comparison objects.

제3도는 비교대상들 중에서 최대치를 구하는 순서도.3 is a flowchart for obtaining the maximum value among the comparison objects.

제4도는 본 발명을 구현하기 위한 전체 블록도.4 is an overall block diagram for implementing the present invention.

제5도는 입력치를 XORing하기 위한 어레이 XOR회로의 회로도.5 is a circuit diagram of an array XOR circuit for XORing an input value.

제6도는 최대ㆍ최소 검색회로의 구현예를 도시한 도면.6 is a diagram showing an embodiment of a maximum and minimum search circuit.

제7도는 최대ㆍ최소 검색회로에 포함되는 그룹 선택기의 구현예를 도시한 도면.7 shows an example of the implementation of a group selector included in the maximum and minimum search circuits.

* 도면의 주요부분에 대한 부호의 설명* Explanation of symbols for main parts of the drawings

10 : 어레이 XOR 회로 20 : 열별배치 회로10: array XOR circuit 20: column-aligned circuit

30 : 최대ㆍ최소 검색회로 31 : 제1어레이 AND 회로30: maximum and minimum search circuit 31: first array AND circuit

32 : 제2어레이 AND 회로 33 : 제3어레이 AND 회로32: second array AND circuit 33: third array AND circuit

34 : 제4어레이 AND 회로 35 : 제5어레이 AND 회로34: fourth array AND circuit 35: fifth array AND circuit

36 : 제6어레이 AND 회로 37 : 그룹 선택기36: sixth array AND circuit 37: group selector

40 : 행렬배치 회로 51 : 제1 OR 회로40: matrix arrangement circuit 51: first OR circuit

52 : 제2 OR 회로 53 : 제3 OR 회로52: second OR circuit 53: third OR circuit

54 : 제4 OR 회로54: fourth OR circuit

61, 62, 63, 64, 65, 66, 67, 68, 71, 72, 73, 74, : XOR 게이트XOR gates: 61, 62, 63, 64, 65, 66, 67, 68, 71, 72, 73, 74,

80. 81, 82, 83, 84, 85, 96, 87, 88 : OR 게이트80, 81, 82, 83, 84, 85, 96, 87, 88: OR gate

91, 92, 93, 94, 95, 96, 97 : ELSEIF 회로91, 92, 93, 94, 95, 96, 97: ELSEIF circuit

상기 목적을 달성하기 위한 본 발명의 특징은 비트맵으로 구성되어 크기가 M일 경우에 제M열 이하의 비트들은 1로 표시하고 제M+1열 이상의 비트들은 0으로 표시하는 비교치들의 최소치를 구하는 비트맵을 이용한 정렬방법에 있어서, 입력된 모든 비교치들을 각각 2개의 인접한 비트끼리 배타적 논리합을 수행하여 열이 하나 더 많은 배타적 논리합된 새로운 비트맵을 만들되 최상위 비트는 하나의 인접한 비트와 배타적 논리합을 수행하며 또한 0과도 배타적 논리합을 수행하고 최하위 비트는 하나의 인접한 비트와 배타적 논리합을 수행하며 또한 1과도 배타적 논리합을 수행하여 상기 비교치들의 크기에 해당하는 열의 비트만이 1의 값을 갖고 그 이외의 비트들은 0의 값을 갖는 상기 새로운 비트맵을 만드는 단계, 비교치들의 최소치를 구하기 위해서 상기 새로운 비트맵에서 최하위 비트부터 시작하여 최상위 비트에 이르기까지 모든 행의 해당 열의 비트들을 검사하되 상기 해당 열의 비트 값이 1인 행이 나타날 때까지 탐색하는 단계 및 상기 탐색단계에서 최초로 상기 해당 열의 비트 값이 1인 행을 찾으면 그 해당 행을 출력하여 비교치들의 최소치가 어떤 행에 있었는지를 알리는 단계로 이루어지는 데에 있다.In order to achieve the above object, a feature of the present invention is composed of a bitmap, and when the size is M, the minimum value of the comparison values indicating bits below the Mth column as 1 and bits above the M + 1th column as 0 are represented. In the sorting method using the obtained bitmap, each of the input comparison values is subjected to an exclusive OR between two adjacent bits, thereby creating a new bitmap with one or more columns, with the most significant bit being an exclusive OR with the adjacent bit. In addition, it performs an exclusive OR with 0, the least significant bit performs an exclusive OR with one adjacent bit, and also performs an exclusive OR with 1, so that only the bits in the column corresponding to the size of the comparisons have a value of 1. Other bits are created in the new bitmap with a value of 0, the value is calculated to obtain the minimum of the comparison values. Inspecting the bits of the corresponding column of all rows starting from the least significant bit to the most significant bit in the new bitmap, searching until the row with the bit value of the corresponding column is 1 and the first bit of the corresponding column in the searching step. When a row with a value of 1 is found, the row is printed to indicate which row had the minimum value of the comparisons.

상기 목적을 달성하기 위한 본 발명의 또 다른 특징은 비트맵으로 구성되어 크기가 M일 경우에 제M열 이하의 비트들은 1로 표시하고 제M+1열 이상의 비트들은 0으로 표시하는 비교치들의 최대치를 구하는 비트맵을 이용한 정렬방법에 있어서, 입력된 모든 비교치들을 각각 2개의 인접한 비트끼리 배타적 논리합을 수행하여 열이 하나 더 많은 배타적 논리합된 새로운 비트맵을 만들되 최상위 비트는 하나의 인접한 비트와 배타적 논리합을 수행하며 또한 0과도 배타적 논리합을 수행하고 최하위 비트는 하나의 인접한 비트와 배타적 논리합을 수행하며 또한 1과도 배타적 논리합을 수행하여 상기 비교치들의 크기에 해당하는 열의 비트만이 1의 값을 갖고 그 이외의 비트들은 0의 값을 갖는 상기 새로운 비트맵을 만드는 단계, 비교치들의 최대치를 구하기 위해서 상기 새로운 비트맵에서 최상위 비트부터 시작하여 최하위 비트에 이르기까지 모든 행의 해당 열의 비트들을 검사하되 상기 해당 열의 비트 값이 1인 행이 나타날 때까지 탐색하는 단계 및 상기 탐색단계에서 최초로 상기 해당 열의 비트 값이 1인 행을 찾으면 그 해당 행을 출력하여 비교치들의 최대치가 어떤 행에 있었는지를 알리는 단계로 이루어지는 데에 있다.Another feature of the present invention for achieving the above object is composed of a bitmap and when the size is M of the comparison value of the bits below the M column is represented by 1 and the bits above the M + 1 column are represented by 0 In the bitmap sorting method to obtain the maximum value, all of the input comparison values are subjected to exclusive OR between two adjacent bits, respectively, to create a new bitmap with one or more columns, with the most significant bit being one adjacent bit. Performs an exclusive OR, and also performs an exclusive OR with 0, the least significant bit performs an exclusive OR with one adjacent bit, and also performs an exclusive OR with 1, so that only the bits in the column corresponding to the size of the comparison values have a value of 1. Creating the new bitmap with the other bits having a value of zero, finding the maximum of the comparisons Checking the bits of the corresponding column of all rows starting from the most significant bit to the least significant bit in the new bitmap, searching until the row with the bit value of the corresponding column is 1; When a row with a bit value of 1 is found, the corresponding row is output to indicate which row has the maximum value of the comparison values.

상기 목적을 달성하기 위한 본 발명의 또 다른 특징은 비트맵으로 구성되어 크기가 M일 경우에 제M열 이하의 비트들은 1로 표시하고 제M+1열 이상의 비트들은 0으로 표시하는 비교치들의 최대치 또는 최소치를 구하는 비트맵을 이용한 정렬방법에 있어서, 입력된 모든 비교치들을 각각 2개의 인접한 비트끼리 배타적 논리합을 수행하여 열이 하나 더 많은 배타적 논리합된 새로운 비트맵을 만들되 최상위 비트는 하나의 인접한 비트와 배타적 논리합을 수행하며 또한 0과도 배타적 논리합을 수행하고 최하위 비트는 하나의 인접한 비트와 배타적 논리합을 수행하며 또한 1과도 배타적 논리합을 수행하여 상기 비교치들의 크기에 해당하는 열의 비트만이 1의 값을 갖고 그 이외의 비트들은 0의 값을 갖는 상기 새로운 비트맵을 만드는 어레이 배타적 논리합 수단, 상기 어레이 배타적 논리합 수단의 출력신호들을 입력받아 열별로 재배치하되 최소치 모드시에는 비트맵의 최하위 비트열들의 신호부터 최상위 비트열들의 신호까지의 순서로 신호의 순서를 재비치하여 최대치 모드시에는 비트맵의 최상위 비트열들의 신호부터 최하위 비트열들의 신호까지의 순서로 신호의 순서를 재배치하여 출력하는 열별배치 수단, 상기 열별배치 수단으로부터 정렬된 비트들을 입력받아서 1의 값을 갖는 비트를 검색하여 가장 먼저 발견된 비트만 1의 값을 유지하도록 하고 나머지 모든 비트들은 0으로 재설정하여 입력된 순서대로 출력하는 최대ㆍ최소 검색수단, 상기 최대ㆍ최소 검색 수단으로부터 차례대로 비트들을 입력받아서 상기 열별 배치 수단에 입력된 입력신호의 순서대로 비트들을 재배치하여 출력하는 행별배치 수단 및 상기 행별배치 수단의 출력 비트들을 행별로 입력받아서 각각의 행에 대하여 열의 갯수만큼의 비트들을 논리합하여 행의 갯수만큼의 출력신호를 출력하되 최소치 모드이면 최소치에 해당하는 비트값만을 1로 출력하고 나머지 비트들은 0으로 출력하며 최대치 모드이면 최대치에 해당하는 비트값만을 1로 출력하고 나머지 비트들은 0으로 출력하는 어레이 논리합 수단으로 구성되며, 조합회로로 구성되어 단일 클럭으로 동작하여 클럭의 갯수에 대한 제약을 줄일 수 있는 데에 있다.Another feature of the present invention for achieving the above object is composed of a bitmap and when the size is M of the comparison value of the bits below the M column is represented by 1 and the bits above the M + 1 column are represented by 0 A bitmap sorting method using the bitmap to find the maximum or minimum value, in which all of the input comparisons are performed by performing an exclusive OR between two adjacent bits, respectively, to create a new bitmap with one or more columns, with the most significant bit being one adjacent. It performs an exclusive OR with a bit, and also an exclusive OR with 0, the least significant bit performs an exclusive OR with one adjacent bit, and also with an 1, performs an exclusive OR with only bits in the column corresponding to the magnitudes of the comparisons. An array-exclusive OR that creates the new bitmap with a value and the other bits have a value of zero. However, the output signals of the array exclusive logical sum means are input and rearranged by columns. In the minimum mode, the signal order is re-arranged in the order of the signals of the least significant bit strings to the signals of the most significant bit strings. Column-alignment means for rearranging and outputting the signals in order from the signals of the most significant bit strings to the signals of the least significant bit strings of the bitmap, and receiving the aligned bits from the column-alignment means to search for bits having a value of 1 Only the first found bits maintain the value of 1, and all the remaining bits are reset to 0 and outputted in the order of input. Row by row rearranging and outputting bits in the order of input signal input to Outputs the output bits of the means and the row-by-row means by row, and logically adds the number of columns for each row and outputs the output signal of the number of rows, but outputs only the bit value corresponding to the minimum value as 1 in the minimum mode. The remaining bits are output as 0. In the maximum mode, only the bit value corresponding to the maximum value is output as 1 and the remaining bits are configured as an array OR means that outputs as 0. It is composed of a combination circuit and operates as a single clock. It is to reduce the restrictions on the system.

이하, 첨부된 도면을 참조하여 본 발명에 따른 바람직한 실시예들 중의 하나를 상세히 설명한다.Hereinafter, with reference to the accompanying drawings will be described in detail one of the preferred embodiments according to the present invention.

제1a도는 비교대상들의 형식을 표시한 비트맵을 나타낸 도면이고, 제1b도는 비교대상들의 4개의 비트맵의 예를 나타낸 도면이고, 제1c도는 비교대상들을 인접한 비트끼리 XORing한 결과를 나타낸 도면이고, 제2도는 비교대상들 중에서 최소치를 구하는 순서도이고, 제3도는 비교대상들 중에서 최대치를 구하는 순서도이다.FIG. 1a is a diagram showing a bitmap indicating the format of comparison objects, FIG. 1b is a diagram showing an example of four bitmaps of comparison objects, and FIG. 1c is a view showing the results of XORing adjacent bits between the comparison objects. 2 is a flowchart for obtaining a minimum value among the comparison objects, and FIG. 3 is a flowchart for obtaining a maximum value among the comparison objects.

제1a도 내지 제3도를 참조하여 행별로 비교대상들을 표시한 비트맵과 비교대상들 중에서 최소치와 최대치를 구하는 방법을 설명하면 다음과 같다.Referring to FIGS. 1A through 3, a method of obtaining a minimum value and a maximum value among the bitmaps and the comparison objects that are displayed for each row are described below.

비교대상들이 4개이며 비교치의 표현범위가 0에서 5이다.There are four objects to be compared, and the range of expression of the comparison value is 0 to 5.

한 행이 하나의 비교대상이며, 1에서 4까지 번호를 매긴 행에 비교대상이 각각 위치한다.One row is the one to be compared, and the comparison is placed in the rows numbered 1 through 4.

이때에, 제L행의 위치에서 비교치의 표현은 제1a도와 같이 B(L,5), B(L,4), B(L,3), B(L,2),, B(L,1)이 된다.At this time, the expression of the comparison value at the position of the Lth row is B (L, 5), B (L, 4), B (L, 3), B (L, 2), B (L, 1) becomes

비교치의 크기가 M일 경우에 제M열 이하의 비트들은 1로 표시하고 제M+1열 이상의 비트들을 0으로 표시한다.When the magnitude of the comparison value is M, bits below the Mth column are represented by 1, and bits above the M + 1th column are represented by 0.

즉, 비교치의 크기가 3이면 제3열 이하의 비트들은 1로 표시하고 제4열 이상의 비트들은 0으로 표시하여 00111이 된다.That is, when the comparison value is 3, bits below the third column are represented by 1 and bits above the fourth column are represented by 0 to be 00111.

먼저, 제2도를 참조하여 비교대상들 중에서 최소치를 찾는 방법부터 설명한다.First, a method of finding a minimum value among the comparison objects will be described with reference to FIG. 2.

최소치의 행을 구하기 위해서 제0열에서 시작하여 제1행부터 제4행까지 행의 오름차순으로 비트 값이 1인 것을 찾는 탐색 작업을 제5열까지 열의 오름차순으로 반복하여 수행하면, 최소치의 행은 최초로 탐색된 비트 위치의 행으로 나타난다.In order to find the minimum row, if the search operation that finds the bit value is 1 in the ascending order of the rows from the first column to the fourth row is repeated, the ascending order of the column to the fifth column is repeated. Appears as the row of the first searched bit position.

S10에서는 제1b도와 같은 비교치들 B(1,1)부터 B(4,5)까지를 입력받는다.In S10, the comparison values B (1,1) to B (4,5) as shown in FIG. 1b are received.

S11에서는 각 비교치들을 각각 2개의 인접한 비트끼리 배타적 논리합(eXclusive ORing, 이하 XORing 또는 XOR로 약칭함)하되, MSB는 하나의 인접한 비트와 XORing을 수행하며 또한 0과도 XORing하고, LSB는 하나의 인접한 비트와 XORing을 수행하며 또한 1과도 XORing하여 제1c도와 같이 C(1,0)부터 C(4,5)를 만든다.In S11, each of the comparison values is an exclusive OR between two adjacent bits (abbreviated as eXclusive ORing, hereinafter referred to as XORing or XOR). It performs XORing with bits and also XORing with 1 to make C (1,0) to C (4,5) as shown in FIG. 1c.

즉, 제1b도의 제1행과 제1c도의 제1행을 예로 들어 설명하면 다음과 같다.That is, the first row of FIG. 1b and the first row of FIG. 1c will be described as follows.

S12에서는 변수M을 0으로 초기화한다.In S12, the variable M is initialized to zero.

S13에서는 변수L을 1로 초기화한다.In S13, the variable L is initialized to 1.

S14에서는 C(L,M)이 1인지 검사한다.In S14, it is checked whether C (L, M) is one.

상기 S14에서C(L,M)이 1이라고 판단되면, S19에서는 L을 출력하고 종료한다.If C (L, M) is determined to be 1 in S14, then L19 outputs L and ends.

상기 S14에서 C(L,M)이 0이라고 판단되면, S15에서는 L이 4인지 검사한다.If C (L, M) is determined to be 0 in S14, it is checked whether L is 4.

상기 S15에서 L이 4보다 작다고 판단되면, S16에서는 L을 1만큼 증가시키고 상기 S14로 진행한다.If it is determined in step S15 that L is less than 4, then in step S16, L is increased by 1 and the process proceeds to S14.

상기 S15에서 L이 4라고 판단되면, S17에서는 M이 5인지 검사한다.When L is determined to be 4 in S15, it is checked whether M is 5 in S17.

상기 S17에서 M이 5보다 작다고 판단되면, S18에서는 M을 1만큼 증가시키고 상기 S13으로 진행한다.If it is determined in step S17 that M is less than 5, then in step S18, M is increased by 1 and the process proceeds to step S13.

상기 S17에서 M이 5라고 판단되면 종료한다.If M is determined to be 5 in step S17, the process ends.

다음으로, 제3도를 참조하여 비교대상들 중에서 최대치를 찾는 방법을 설명한다.Next, a method of finding the maximum value among the comparison objects will be described with reference to FIG. 3.

최대치의 행을 구하기 위해서 5열에서 시작하여 1행부터 4행까지 행의 오름차순으로 비트 값이 1인 것을 찾는 탐색 작업을 0열까지 열의 내림차순으로 반복 수행하면, 최대치의 행은 최초로 탐색된 비트 위치의 행으로 나타난다.To find the maximum row, if you repeat the search operation starting from column 5 to find the bit value 1 in rows 1 to 4 in ascending order of rows, the maximum row is the first bit position found in column descending order. Appears as a row of

S20에서는 제1b도와 같은 비교치들 B(1,1)부터 B(4,5)까지를 입력받는다.In S20, the comparison values B (1,1) to B (4,5) as shown in FIG. 1b are received.

S21에서는 각 비교치들을 인접한 비트끼리 XORing하되, MSB는 0과 XORing하고 LSB는 1과 XORing하여 제1c도와 같이 C(1,0)부터 C(4,5)를 만든다.In S21, each comparison value is XORing adjacent bits, MSB is XORing with 0, and LSB is XORing with 1 to make C (1,0) to C (4,5) as shown in FIG. 1c.

S22에서는 변수 M을 5로 초기화한다.In S22, the variable M is initialized to 5.

S23에서는 변수 L을 1로 초기화한다.In S23, the variable L is initialized to 1.

S24에서는 C(L,M)이 1인지 검사한다.In S24, it is checked whether C (L, M) is one.

상기 S24에서 C(L,M)이 1이라고 판단되면, S29에서는 L을 출력하고 종료한다.If C (L, M) is determined to be 1 in S24, then L29 outputs L and ends.

상기 S24에서 C(L,M)이 0이라고 판단되면, S25에서는 L이 4인지 검사한다.If C (L, M) is determined to be 0 in S24, it is checked whether L is 4 in S25.

상기 S25에서 L이 4보다 작다고 판단되면, S26에서는 L을 1만큼 증가시키고 상기 S24로 진행한다.If it is determined in step S25 that L is less than 4, then in step S26 L is increased by 1 and the process proceeds to S24.

상기 S25에서 L이 4라고 판단되면, S27에서는 M이 0인지 검사한다.When L is determined to be 4 in S25, it is checked in step S27 that M is 0.

상기 S27에서 M이 0이 아니라고 판단되면, S28에서는 M을 1만큼 감소시키고 상기 S23으 로 진행한다.If it is determined in step S27 that M is not 0, in step S28, M is decreased by 1 and the process proceeds to step S23.

상기 S27에서 M이 0이라고 판단되면, 종료한다.If M is determined to be 0 in S27, the process ends.

즉, 최소치의 탐색시에 비교치들 중 가장 작은 것에 해당되는 제2행은 제0열에서 제일 먼저 탐색된 1의 값을 갖는 비트의 행이며, 최대치의 탐색시에 가장 큰 것에 해당되는 제3행은 제5열에서 제일 먼저 탐색된 1의 값을 갖는 비트의 행이다.That is, the second row corresponding to the smallest of the comparison values at the minimum search is the row of bits having a value of 1 searched first in column 0, and the third row corresponding to the largest at the maximum search. Is a row of bits with a value of 1 searched first in column 5.

제4도는 본 발명을 구현한 전체 블록도이다.4 is a block diagram showing the implementation of the present invention.

제4도를 참조하여 본 발명의 하드웨어적인 구현을 설명하면 다음과 같다.Referring to Figure 4 describes the hardware implementation of the present invention.

어레이 XOR회로(10)는 XOR의 조합회로로 구성되어, 입력된 비교치 B(L,M)의 인접한 비트끼리 XORing하여 C(L,M)을 만들어 출력한다.The array XOR circuit 10 is composed of a combination circuit of XOR, and XORing adjacent bits of the input comparison value B (L, M) to generate and output C (L, M).

MSB인 B(L,5)는 0과 XORing하여 C(L,5)가 되고 B(L,4)와 XORing하여 C(L,4)가 되며, LSB인 B(L,1)은 B(L,2)와 XORing하여 C(L,1)이 되고 1과 XORing하여 C(L,0)이 된다.B (L, 5), MSB, becomes C (L, 5) by XORing with 0, and C (L, 4) by XORing with B (L, 4), and B (L, 1), LSB, XORing with L, 2) results in C (L, 1) and XORing with 1 results in C (L, 0).

제5도에서처럼 어레이 XOR 회로에서 제1행에서 제4행까지 비교치를 나타내는 비트맵을 입력하여 {1, B(1,1), B(1,2), B(1,3), B(1,4), B(1,5), 0}, {1, B(2,1), B(2,2), B(2,3), B(2,4), B(2,5), 0},{1, B(3,1), B(3,2), B(3,3), B(3,4), B(3,5),0}, {1, B(4,1), B(4,2), B(4,3), B(4,4), B(4,5),0}로 구성된 비트맵을 인접한 비트끼리 XORing하면 각 행별로 0과 1의 경계 비트만이 1의 값을 갖고 나머지 비트들은 0의 값을 갖는 비트맵 C(1,0), C(1,1), C(1,2), C(1,3), C(1,4), C(1,5), C(2,0), C(2,1), C(2,3), C(2,4), C(2,5), C(3,0), C(3,1), C(3,2), C(3,3), C(3,4), C(3,5), C(4,1), C(4,1) C(4,2), C(4,3), C(4,4), C(4,5)가 출력된다.As shown in FIG. 5, in the array XOR circuit, a bitmap representing a comparison value from the first row to the fourth row is inputted so that {1, B (1,1), B (1,2), B (1,3), B ( 1,4), B (1,5), 0}, {1, B (2,1), B (2,2), B (2,3), B (2,4), B (2, 5), 0}, {1, B (3,1), B (3,2), B (3,3), B (3,4), B (3,5), 0}, {1, When XORing bitmaps consisting of B (4,1), B (4,2), B (4,3), B (4,4), B (4,5), 0} between adjacent bits, Bitmaps C (1,0), C (1,1), C (1,2), C (1,3) with only 0 and 1 boundary bits having a value of 1 and the remaining bits having a value of 0 , C (1,4), C (1,5), C (2,0), C (2,1), C (2,3), C (2,4), C (2,5), C (3,0), C (3,1), C (3,2), C (3,3), C (3,4), C (3,5), C (4,1), C (4,1) C (4,2), C (4,3), C (4,4), C (4,5) are output.

즉, C(L,M)에서 1의 값을 갖는 비트의 위치가 B(L,M)의 크기를 표현하게 된다.That is, the position of the bit having a value of 1 in C (L, M) represents the size of B (L, M).

열별배치 회로(20)는 최소치를 구하는 모드와 최대치를 구하는 모드의 두가지 모드를 가지고 있는데, 어레이 XOR 회로(10)로부터 C(1,0)에서 C(4,5)까지 입력받아 열별로 재배치하여 출력하는 회로이다.The column arrangement circuit 20 has two modes, a mode for finding the minimum value and a mode for obtaining the maximum value. The column-aligned circuit 20 receives inputs from C (1,0) to C (4,5) from the array XOR circuit 10 and rearranges them by column. It is an output circuit.

이는 C(1,0)에서 C(4,5)까지의 입력단과 Q1에서 Q24까지의 출력단 사이의 연결관계를 구성하는 선들만으로 이루어진 회로이다.This circuit consists of only the lines forming the connection between the input terminals C (1,0) to C (4,5) and the output terminals Q1 to Q24.

최소치 모드시에는 비트맵의 제0열부터 시작하여, 각 열에 대하여 제1행부터 제4행까지의 행의 오름차순으로 비트를 재배치하여 제5열까지 열의 오름차순으로 반복수행하여 정렬된 비트들을 출력한다.In the minimum mode, the bits are rearranged in the ascending order of the rows from the first row to the fourth row of the bitmap, starting from the 0th column of the bitmap, and repeatedly arranged in the ascending order of the columns to the 5th column, and the sorted bits are output. .

열별배치 회로(20)에 의하여, C(1,0), C(2,0), C(3,0) 및 C(4,0)은 각각 Q1, Q2, Q3 및 Q4로 되고, C(1,1), C(2,1), C(3,1) 및 C(4,1)은 각각 Q5 Q6 Q7 및 Q8로 되고, C(1,2), C(2,2), C(3,2) 및 C(4,2)는 각각 Q9 Q10 Q11 및 Q12로 되고, C(1,3), C(2,3), C(3,3) 및 C(4,3)은 각각 Q13, Q14, Q15 및 Q16으로 되고, C(1,4), C(2,4), C(3,4) 및 C(4,4)는 각각 Q17, Q18, Q19 및 Q20으로 되며, C(1,5), C(2,5), C(3,5) 및 C(4,5)는 각각 Q21, Q22, Q23 및 Q24로 된다.By the column-alignment circuit 20, C (1,0), C (2,0), C (3,0) and C (4,0) become Q1, Q2, Q3 and Q4, respectively, and C ( 1,1), C (2,1), C (3,1) and C (4,1) are Q5 Q6 Q7 and Q8, respectively, and C (1,2), C (2,2), C (3,2) and C (4,2) are Q9 Q10 Q11 and Q12, respectively, C (1,3), C (2,3), C (3,3) and C (4,3) Q13, Q14, Q15 and Q16, respectively, C (1,4), C (2,4), C (3,4) and C (4,4) are Q17, Q18, Q19 and Q20, respectively. C (1,5), C (2,5), C (3,5) and C (4,5) are Q21, Q22, Q23 and Q24, respectively.

최대치 모드에서는 비트맵의 제5열부터 시작하여, 각 열에 대하여 제1행부터 제4행까지 행의 오름차순으로 비트를 재배치하여 제0열까지 열의 내림차순으로 반복수행하여 정렬된 비트들을 출력한다.In the maximum mode, the bits are rearranged in the ascending order of the rows from the first row to the fourth row, starting from the fifth column of the bitmap, and repeatedly arranged in the descending order of the column to the zeroth column, and output the aligned bits.

열별배치 회로(20)에 의하여, C(1,5), C(2,5), C(3,5) 및 C(4,5)은 각각 Q1, Q2, Q3 및 Q4로 되고, C(1,4), C(2,4), C(3,4) 및 C(4,4)은 각각 Q5 Q6 Q7 및 Q8로 되고, C(1,3), C(2,3), C(3,3) 및 C(4,3)는 각각 Q9 Q10 Q11 및 Q12로 되고, C(1,2), C(2,2), C(3,2) 및 C(4,2)은 각각 Q13, Q14, Q15 및 Q16으로 되고, C(1,1), C(2,1), C(3,1) 및 C(4,1)는 각각 Q17, Q18, Q19 및 Q20으로 되며, C(1,0), C(2,0), C(3,0) 및 C(4,0)는 각각 Q21, Q22, Q23 및 Q24로 된다.By the column-alignment circuit 20, C (1,5), C (2,5), C (3,5) and C (4,5) become Q1, Q2, Q3 and Q4, respectively, and C ( 1,4), C (2,4), C (3,4) and C (4,4) are Q5 Q6 Q7 and Q8, respectively, and C (1,3), C (2,3), C (3,3) and C (4,3) are Q9 Q10 Q11 and Q12, respectively, C (1,2), C (2,2), C (3,2) and C (4,2) Q13, Q14, Q15 and Q16, respectively, C (1,1), C (2,1), C (3,1) and C (4,1) are Q17, Q18, Q19 and Q20, respectively. C (1,0), C (2,0), C (3,0) and C (4,0) are Q21, Q22, Q23 and Q24, respectively.

최대ㆍ최소 검색회로(30)는 Q1부터 Q24까지 차례로 1이 있는지 스캐닝하면서 1을 찾다가 1을 발견하면 스캐닝을 중단하고 해당 비트만 1을 출력하고 나머지는 0을 출력한다.The maximum and minimum retrieval circuit 30 scans 1 from Q1 to Q24 sequentially to find 1, and if it finds 1, stops scanning, outputs only 1 corresponding bit, and outputs 0 for the rest.

즉,Q1부터 Q10까지 0이었고 Q11에서 1이 발견되었으며, Q11에 해당되는 R11만 1DMF 출력하고 나머지 R1부터 R10까지와 R12부터 R24까지는 0을 출력한다.That is, it is 0 from Q1 to Q10 and 1 is found in Q11. Only R11 corresponding to Q11 is outputted by 1DMF and 0 is output from the remaining R1 to R10 and R12 to R24.

행별배치 회로(40)는 R1에서 R24까지의 입력단과 S(1,0)에서 S(4,5)까지의 출력단 사이에 연결관계를 구성하는 선들만으로 이루어진 회로이다.The row arrangement circuit 40 is a circuit composed only of lines forming a connection relationship between an input terminal of R1 to R24 and an output terminal of S (1,0) to S (4,5).

이는 비트 제0열에서 최대 비트 제5열까지 열별로 정리된 여섯 묶음인(,R1, R2, R3, R4), (R5, R6, R7, R8), (,R9, R10, R11, R12), (R13, R14, R15, R16), (R17, R18, R19, R20), (R21, R22, R23, R24)를 행별로 정리된 묶음으로 변환하기 위해 제1행에서 시작하여, 각 행에 대하여 제0열부터 제5열까지 열의 오름차순으로 비트를 재배치하여 제4행까지 행의 오름차순으로 반복수행한다.This is a six-column (, R1, R2, R3, R4), (R5, R6, R7, R8), (, R9, R10, R11, R12) arranged in columns from bit 0 to max. , Starting from the first row to convert (R13, R14, R15, R16), (R17, R18, R19, R20), (R21, R22, R23, R24) into a batch organized row by row, On the other hand, the bits are rearranged in the ascending order of the columns from the 0th column to the 5th column, and are repeatedly executed in the ascending order of the rows up to the fourth row.

즉, 행별배치 회로(40)에 의하면, R1, R5, R9, R13, R17, R21은 제1행의 묶음인 S(1,0)∼S(1,5)로 되며, R2, R6, R10, R14, R18, R22은 제2행의 묶음인 S(2,0)∼S(2,5)로 되고, R3, R7, R11, R15, R17, R23은 제3행의 묶음인 S(3,0)∼S(3,5)로 되며, R4, R8, R12, R16, R20, R24은 제4행의 묶음인 S(4,0)∼S(4,5)로 된다.That is, according to the row arrangement circuit 40, R1, R5, R9, R13, R17, and R21 are S (1,0) to S (1,5), which are bundles of the first row, and R2, R6, R10. , R14, R18, and R22 are S (2,0) to S (2,5) which are bundles of the second row, and R3, R7, R11, R15, R17, and R23 are bundles of S (3) which are the third row bundle , 0) to S (3,5), and R4, R8, R12, R16, R20, and R24 are S (4,0) to S (4,5), which are bundles of the fourth row.

제1OR회로(51)는 S(1,0)∼S(1,5)를 논리합(ORing)을 수행하며 U1을 출력하고, 제2OR회로(52)는 S(2,0)∼S(2,5)를 ORing하여 U2를 출력하며, 제3OR회로(53)는 S(3,0)∼S(3,5)를 ORing하여 U3를 출력하고, 제4OR회로(54)는 S(4,0)∼S(4,5)를 ORing하여 U4를 출력한다.The first OR circuit 51 performs an ORing of S (1,0) to S (1,5) and outputs U1, and the second OR circuit 52 performs an S (2,0) to S (2) operation. OR5, to output U2, and the third OR circuit 53 ORs S (3,0) to S (3,5) to output U3, and the fourth OR circuit 54 outputs S (4, ORing 0) to S (4,5) to output U4.

제5도는 입력치를 XORing하기 위한 어레이 XOR 회로의 회로도이다.5 is a circuit diagram of an array XOR circuit for XORing an input value.

제5도를 참조하여 입력치를 XORing하기 위한 어레이 XOR 회로에 관하여 설명하면 다음과 같다.An array XOR circuit for XORing an input value with reference to FIG. 5 will now be described.

어레이 XOR 회로(10)는 XOR 회로를 어레이로 배열하여 만들어지는데, 비트맵의 비교치들을 각각 입력받아 인접한 비트끼리 XOR한다.The array XOR circuit 10 is formed by arranging the XOR circuits in an array. The array XOR circuits 10 receive the comparison values of the bitmaps and XOR adjacent bits.

제1행을 예로 들면, XOR 회로(65)는 B(1,5)와 B(1,4)을 받아 입력받아 XORing하여 C(1,4)을 출력하고, XOR 회로(66)는 B(1,4)와 B(1,3)을 받아 입력받아 XORing하여 C(1,3)을 출력하고, XOR 회로(67)는 B(1,3)와 B(1,2)을 받아 입력받아 XORing하여 C(1,2)을 출력하고, XOR 회로(68)는 B(1,2)와 B(1,1)을 받아 입력받아 XORing하여 C(1,1)을 출력한다.Taking the first row as an example, the XOR circuit 65 receives B (1,5) and B (1,4), receives XORing to output C (1,4), and the XOR circuit 66 outputs B ( Takes 1,4) and B (1,3) and XORing to output C (1,3), XOR circuit 67 receives B (1,3) and B (1,2) XORing outputs C (1,2), and the XOR circuit 68 receives B (1,2) and B (1,1), receives XORing, and outputs C (1,1).

그리고, XOR 회로(61∼64)는 MSB인 B(1,5), B(2,5), B(3,5) 및 B(4,5)를 각각 입력받아 논리 '0'과 각각 XORing하여 C(1,5), C(2,5), C(3,5) 및 C(4,5)를 각각 출력한다.The XOR circuits 61-64 receive B (1,5), B (2,5), B (3,5), and B (4,5), respectively, which are MSBs. Output C (1,5), C (2,5), C (3,5) and C (4,5), respectively.

또한, XOR회로(71∼74)는 MSB인 B(1,1), B(2,1), B(3,1) 및 B(4,1)를 각각 입력받아 논리 '1'과 각각 XORing하여 C(1,0), C(2,0), C(3,0) 및 C(4,0)를 각각 출력한다.Also, the XOR circuits 71 to 74 receive B (1,1), B (2,1), B (3,1), and B (4,1), which are MSBs, respectively, and the logic '1' and XORing respectively. To output C (1,0), C (2,0), C (3,0) and C (4,0), respectively.

제6도는 최대ㆍ최소 검색회로의 구현예를 도시한 도면이다.6 is a diagram showing an embodiment of the maximum and minimum search circuits.

제6도를 참조하여 최대ㆍ최소 검색회로의 구현예를 설명하면 다음과 같다.An embodiment of the maximum and minimum search circuits will be described with reference to FIG.

최대ㆍ최소 검색회로(30)는 입력으로 1의 값을 갖는 Q1에서 Q24까지의 비트들 중에서 가장 먼저 위치한 것만이 1이 되고 나머지는 0이 되도록하여 R1에서 R24까지를 출력하는 회로이다.The maximum and minimum retrieval circuit 30 is a circuit for outputting R1 to R24 so that only the first one of the bits from Q1 to Q24 having a value of 1 becomes 1 and the rest is 0.

그렇게 하기 위해, 그룹 선택기(37)는 출력단 G0∼G5중에서 처음으로 1이 나온 열의 그룹을 나타내는 출력단을 1로 출력하고 나머지 출력단들은 0으로 출력한다.To do so, the group selector 37 outputs an output terminal representing the group of the first column of outputs G0 to G5 as 1 and the remaining output terminals as 0.

제1어레이 AND 회로(31)에서는 Q1∼Q4가 각각 G0과 논리곱(ANDing)되어 각각 R1∼R4가 출력되고, 제2어레이 AND 회로(32)에서는 Q5∼Q8가 각각 G1과 ANDing되어 각각 R5∼R8가 출력되며, 제3어레이 AND 회로(33)에서는 Q9∼Q12가 각각 G2과 ANDing되어 각각 R9∼R12가 출력되고, 제4어레이 AND 회로(34)에서는 Q13∼Q16가 각각 G3과 ANDing되어 각각 R13∼R16가 출력되며, 제5어레이 AND 회로(35)에서는 Q17∼Q20가 각각 G4과 ANDing되어 각각 R17∼R20가 출력되고, 제6어레이 AND 회로(36)에서는 Q21∼Q24가 각각 G5과 ANDing되어 각각 R21∼R24가 출력된다.In the first array AND circuit 31, Q1 to Q4 are ANDed with G0, respectively, to output R1 to R4, respectively. In the second array AND circuit 32, Q5 to Q8 are ANDed with G1, respectively, and R5 respectively. To R8 are output, and in the third array AND circuit 33, Q9 to Q12 are ANDed with G2, respectively, and R9 to R12 are output, respectively, and in the fourth array AND circuit 34, Q13 to Q16 are ANDed with G3, respectively. R13 to R16 are output, respectively, and in the fifth array AND circuit 35, Q17 to Q20 are ANDed with G4, respectively, and R17 to R20 are output, respectively. In the sixth array AND circuit 36, Q21 to Q24 are respectively represented with G5 and G5. ANDing is performed to output R21 to R24, respectively.

제7도는 최대ㆍ최소 검색회로에 포함되는 그룹 선택기의 구현예를 도시한 도면이다.7 is a diagram showing an embodiment of a group selector included in the maximum and minimum search circuits.

제7도는 참조하여 최대ㆍ최소 검색회로에 포함되는 그룹 선택기(37)의 구현예를 설명하면 다음과 같다.Referring to FIG. 7, an embodiment of the group selector 37 included in the maximum and minimum search circuits will be described below.

그룹 선택기(37)에 입력된 Q1∼Q24는 Q1∼Q4, Q5∼Q8, Q9∼Q12, Q13∼Q16, Q17∼Q20 및 Q21∼Q24의 6그룹으로 나뉘어 같은 그룹끼리 ORing되는데, OR 회로(80)에서는 Q1∼Q4가 ORing되어 E0이 출력되고, OR 회로(81)에서는 Q5∼Q8가 ORing되어 E1이 출력되며, OR 회로(82)에서는 Q9∼Q12가 ORing되어 E2이 출력되고, OR 회로(83)에서는 Q13∼Q16가 ORing되어 E3이 출력되며, OR 회로(84)에서는 Q17∼Q20가 ORing되어 E4이 출력되고, OR 회로(85)에서는 Q21∼Q24가 ORing되어 E5이 출력된다.Q1 to Q24 input to the group selector 37 are divided into six groups of Q1 to Q4, Q5 to Q8, Q9 to Q12, Q13 to Q16, Q17 to Q20, and Q21 to Q24, and ORing is performed on the same groups. ) Q1 to Q4 are ORed to output E0, OR circuit 81 to Q5 to Q8 is ORed to output E1, OR circuit 82 to Q9 to Q12 is ORed to output E2, and OR circuit ( In 83), Q13 to Q16 are ORed to output E3. In the OR circuit 84, Q17 to Q20 are ORed to output E4. In the OR circuit 85, Q21 to Q24 are ORed to output E5.

OR 회로(80)의 출력인 E0은 그대로 G0이 되어 출력되어, G0=E0이 된다.E0, the output of the OR circuit 80, is output as G0 as it is, and G0 = E0.

ELSEIF 회로(91)에서 E0이 인버팅되고 인버팅 된 E0/과 E1이 ANDing되어 G1이 되어 출력되어, G1=E0/AND E1된다.In the ELSEIF circuit 91, E0 is inverted, the inverted E0 / and E1 are ANDed and output as G1, and G1 = E0 / AND E1.

OR 회로(86)에서 E0과 E1이 ORing되고, ELSEIF 회로(92)에서 OR회로(86)의 출력이 인버팅 되고 인버팅 된 것과 E2가 ANDing되어 G2가 출력된다.In the OR circuit 86, E0 and E1 are ORed, and in the ELSEIF circuit 92, the output of the OR circuit 86 is inverted and inverted, E2 is ANDed and G2 is output.

즉, G2=(E0 OR E1)/AND E2이다.That is, G2 = (E0 OR E1) / AND E2.

그리고, G3=(E0 OR E1 E2)/AND E3이다.And G3 = (E0 OR E1 E2) / AND E3.

G4=(E0 OR E1 OR E2)/AND (E3/AND E4)이다.G4 = (E0 OR E1 OR E2) / AND (E3 / AND E4).

G5=(E0 OR E1 OR E2)/ AND (E3 OR E4)/ AND E5이다.G5 = (E0 OR E1 OR E2) / AND (E3 OR E4) / AND E5.

먼저, E0이 1인 경우를 설명한다.First, the case where E0 is 1 will be described.

물론, G0은 1의 값을 나타낸다.Of course, G0 represents a value of 1.

E0의 1의 값이 ELSEIF 회로(91)의 출력을 0으로 만들어서 G1이 0의 값을 나타내게 한다.A value of 1 in E0 causes the output of the ELSEIF circuit 91 to be zero so that G1 represents a value of zero.

E0의 1의 값이 OR 회로(86)의 출력을 1로 만들어서 ELSEIF 회로(92)의 출력을 0으로 만들어 G2가 0의 값을 나타내게 한다.A value of 1 in E0 makes the output of the OR circuit 86 equal to 1, causing the output of the ELSEIF circuit 92 to be zero, causing G2 to represent a value of zero.

E0의 1의 값이 OR 회로(87)의 출력을 1로 만들어서 ELSEIF 회로(95.96,97)의 출력을 모두 0으로 만들어 G3, G4, G5가 0의 값을 갖게 한다.A value of 1 in E0 makes the output of the OR circuit 87 equal to 1, which causes all of the outputs of the ELSEIF circuits 95.96 and 97 to be zero so that G3, G4 and G5 have a value of zero.

다음으로, E0이 0이고 E1이 1인 경우를 설명한다.Next, the case where E0 is 0 and E1 is 1 will be described.

물론, G0은 0의 값을 나타낸다.Of course, G0 represents a value of zero.

E0의 0의 값을 E1의 1의 값이 ELSEIF 회로(91)의 출력을 1로 만들어 G1이 1의 값을 나타내게 한다.A value of 0 in E0 makes a value of 1 in E1 cause the output of the ELSEIF circuit 91 to be 1 so that G1 represents a value of 1.

E1의 1의 값이 OR 회로(86)의 출력을 1로 만들어 ELSEIF 회로(92)의 출력을 0으로 만들어 G2가 0의 값을 나타내게 한다.A value of 1 in E1 makes the output of the OR circuit 86 equal to 1 and makes the output of the ELSEIF circuit 92 zero, causing G2 to represent a value of zero.

E1의 1의 값이 OR 회로(87)의 출력을 1로 만들어서 ELSEIF 회로(95,96,97)의 출력을 0으로 만들어 G3, G4, G5를 모두 0의 값을 나타내게 한다.A value of 1 of E1 makes the output of the OR circuit 87 equal to 1, which makes the output of the ELSEIF circuits 95, 96, and 97 zero, so that all of G3, G4, and G5 represent the value of zero.

다음으로, E0과 E1이 모두 0이고 E2가 1인 경우를 설명한다.Next, the case where both E0 and E1 are 0 and E2 is 1 will be described.

E1의 0의 값이 ELSEIF 회로(91)의 출력을 0으로 만들어 G1은 0의 값을 나타낸다.A value of zero in E1 makes the output of the ELSEIF circuit 91 zero, and G1 represents a value of zero.

E0과 E1의 0의 값이 OR 회로(86)의 출력을 0으로 만들어 ELSEIF 회로(92)의 출력을 E2의 값인 1로 만들어 G2가 1의 값을 나타내게 한다.The zero values of E0 and E1 make the output of the OR circuit 86 zero, and make the output of the ELSEIF circuit 92 1, which is the value of E2, so that G2 represents a value of 1.

E2의 1의 값이 OR 회로(87)의 출력을 1로 만들어서 ELSEIF 회로(95,96,97)의 출력을 0으로 만들어 G4, G5, G6를 모두 0의 값을 갖게 한다.A value of 1 in E2 makes the output of the OR circuit 87 equal to 1, thereby making the output of the ELSEIF circuits 95, 96, and 97 zero, so that G4, G5, and G6 all have a value of zero.

다음으로, E0, E1 및 E2가 모두 0이고 E3가 1인 경우를 설명한다.Next, the case where E0, E1 and E2 are all 0 and E3 is 1 will be described.

E2의 0의 값이 ELSEIF 회로(92)의 출력을 0으로 만들어 G2은 0의 값을 나타낸다.A value of zero in E2 makes the output of the ELSEIF circuit 92 zero, and G2 represents a value of zero.

E0, E1, E2의 0의 값이 OR 회로(87)의 출력을 0으로 만들어 ELSEIF 회로(95)의 출력이 E3의 값인 1이 되어 G3은 1의 값을 나타낸다.A value of 0 of E0, E1, E2 makes the output of the OR circuit 87 zero, and the output of the ELSEIF circuit 95 becomes 1, which is the value of E3, and G3 represents the value of 1.

E3의 1의 값이 ELSEIF 회로(93)의 출력을 0으로 만들고, 이는 ELSEIF 회로(96)의 출력을 0의 값으로 만들어 G5은 0의 값을 나타낸다.A value of 1 of E3 makes the output of the ELSEIF circuit 93 zero, which makes the output of the ELSEIF circuit 96 a value of zero, and G5 represents a value of zero.

E3의 1의 값이 OR 회로(88)의 출력을 1로 만들고, 이는 ELSEIF 회로(94)의 출력을 0으로 만들어 ELSEIF 회로(97)의 출력을 0의 값으로 만듦으로써 G5은 0의 값을 갖게 된다.A value of 1 in E3 makes the output of the OR circuit 88 equal to 1, which makes the output of the ELSEIF circuit 94 equal to zero and makes the output of the ELSEIF circuit 97 equal to zero so that G5 returns a value of zero. Will have

다음으로, E0, E1, E2 및 E3가 모두 0이고 E4가 1인 경우를 설명한다.Next, the case where E0, E1, E2 and E3 are all 0 and E4 is 1 will be described.

E3의 0의 값이 ELSEIF 회로(95)의 출력을 0으로 만들어 G3은 0의 값을 나타낸다.A value of zero in E3 makes the output of the ELSEIF circuit 95 zero, and G3 represents a value of zero.

E0, E1 및 E2의 0의 값이 OR 회로(87)의 출력을 0으로 만들고 E3의 0의 값이 ELSEIF 회로(93)의 출력을 E4의 값인 1로 만들기 때문에, ELSEIF 회로(96)의 출력이 1로 만들어져서 G4는 1의 값을 나타낸다.The output of the ELSEIF circuit 96 because the zero values of E0, E1 and E2 make the output of the OR circuit 87 zero and the zero value of E3 makes the output of the ELSEIF circuit 93 1, which is the value of E4. Made of 1, G4 represents the value of 1.

E4의 1의 값이 OR 회로(88)의 출력을 1로 만들고, 이는 ELSEIF 회로(94)의 출력을 0으로 만들고 ELSEIF 회로(97)의 출력을 0의 값으로 만듦으로써 G5는 0의 값을 갖게 된다.A value of 1 in E4 makes the output of the OR circuit 88 1, which makes the output of the ELSEIF circuit 94 zero and the output of the ELSEIF circuit 97 zero, thereby making G5 zero. Will have

끝으로, E0, E1, E2, E3 및 E4가 모두 0이고 E5가 1인 경우를 설명한다.Finally, the case where E0, E1, E2, E3 and E4 are all 0 and E5 is 1 will be described.

E4의 0의 값이 ELSEIF 회로(93)의 출력을 0으로 만들고, 이는 ELSEIF 회로(96)의 출력을 0으로 만들어 G4는 0의 값을 나타낸다.A value of zero in E4 makes the output of the ELSEIF circuit 93 zero, which makes the output of the ELSEIF circuit 96 zero, and G4 represents a value of zero.

E0, E1 및 E2의 0의 값이 OR 회로(87)의 출력을 0으로 만들고 E3과 E4의 0의 값이 OR 회로(88)의 출력을 0으로 만들기 때문에, ELSEIF 회로(94)의 출력을 E5의 값인 1로 만들어 ELSEIF 회로(97)의 출력을 1로 만듦으로써 G5는 1의 값을 갖게 된다.Since the values of 0 in E0, E1 and E2 make the output of OR circuit 87 zero and the values of E3 and E4 make the output of OR circuit 88 zero, the output of ELSEIF circuit 94 By making it 1, which is the value of E5, and making the output of the ELSEIF circuit 97 1, G5 has a value of 1.

그러므로, 상술한 바와 같은 본 발명은 패킷 스위칭시에 최소치의 큐를 찾을 필요성이 있는 고속 패킷 스위치에서 패킷 스위칭 시간을 줄일 수 있고, 멀티 병렬 버퍼의 구현에 있어서도 클럭의 갯수에 대한 제약을 줄일 수 있다는 데에 그 효과가 있다.Therefore, the present invention as described above can reduce the packet switching time in the high-speed packet switch that needs to find the minimum queue at the time of packet switching, and can reduce the constraint on the number of clocks even in the implementation of the multi-parallel buffer. It has an effect.

Claims

In the sorting method using a bitmap that obtains the minimum value of the comparison values consisting of a bitmap and the bits below the Mth column are represented by 1 and the bits above the M + 1th column are represented by 0 when the size is M. All the comparisons are performed by performing an exclusive OR between two adjacent bits, respectively, to create a new bitmap with one or more columns, except that the most significant bit performs an exclusive OR with one adjacent bit, and also performs an exclusive OR with 0. The least significant bit performs an exclusive OR with one adjacent bit and also performs an exclusive OR with 1 so that only the bits of the column corresponding to the size of the comparison values have a value of 1 and the other bits have a value of 0. Creating a bitmap; Examining the bits of the corresponding column of every row starting from the least significant bit to the most significant bit in the new bitmap to find the minimum of the comparisons, and searching until a row with a bit value of 1 in the corresponding column appears; And searching for a row having a bit value of 1 in the search column for the first time, and outputting the corresponding row to indicate in which row the minimum value of the comparison values was located.

In the sorting method using a bitmap that obtains the maximum value of the comparison value consisting of a bitmap and the bit below the M-th column is represented by 1 and the bit above the M + 1 column is represented by 0 when the size is M. Performs an exclusive OR between two adjacent bits, each of which makes a new bitmap with one more exclusive OR of columns, with the most significant bit performing an exclusive OR with one adjacent bit, and also an exclusive OR with zero. The least significant bit performs an exclusive OR with one adjacent bit, and also performs an exclusive OR with 1 so that only the bits of the column corresponding to the sizes of the comparisons have a value of 1 and the other bits have a value of 0. Creating the new bitmap; Examining the bits of the corresponding column of every row from the most significant bit to the least significant bit in the new bitmap to find the maximum of the comparisons, and searching until a row with a bit value of 1 in that column appears; And when the first row is found in the search step, the row having the bit value of 1 is output, and the row is output to indicate which row the maximum value of the comparison values is.

In the sorting device using a bitmap that is composed of a bitmap and the size is M, bits below the Mth column are represented by 1 and bits above the M + 1th column are represented by 0. In addition, each of the input comparisons is performed with an exclusive OR between two adjacent bits, respectively, to create a new bitmap with one more exclusive OR of columns, with the most significant bit performing an exclusive OR with one adjacent bit, and also an exclusive OR with 0. , The least significant bit performs an exclusive OR with one adjacent bit, and also performs an exclusive OR with 1 so that only the bits of the column corresponding to the sizes of the comparisons have a value of 1 and the other bits have a value of 0. Array exclusive OR means for producing the new bitmap with a value; Receives the output signals of the array exclusive logical sum means and rearranges them by column. In the minimum mode, the order of signals is rearranged in order from the signal of the least significant bit strings to the signals of the most significant bit strings. Column-specific arrangement means for rearranging and outputting the order of the signals in the order from the signals of the most significant bit strings to the signals of the least significant bit strings of the map; Search for bits with a value of 1 by receiving the sorted bits from the column-alignment means, so that only the first bits found are maintained at the value of 1, and all other bits are reset to 0 and output in the order entered. Search means; Row arrangement means for receiving bits from the maximum and minimum search means in order and rearranging and outputting the bits in order of input signals input to the column arrangement means; And outputting the output signals as many as the number of rows by receiving the output bits of the row-aligning means for each row and logically adding the number of bits for each row to each row, but in the minimum mode, only the bit value corresponding to the minimum value is 1; Outputting the remaining bits to 0, and in the maximum mode, array bit OR means for outputting only the bit value corresponding to the maximum value as 1 and the remaining bits as 0; It is composed of a combination circuit to operate as a single clock to reduce the restriction on the number of clocks, the alignment device using a bitmap.