RU163442U1 - DEVICE FOR PARALLEL SEARCH FOR COMPOSITE SAMPLE - Google Patents

Abstract

A device for parallel search of a composite sample containing the first and second blocks for storing and comparing associative signs, a logical vector memory block and an operation block, the information inputs of the first and second blocks for storing and comparing associative signs are the first and second information inputs of the device, and the outputs of the storage blocks and comparisons of associative features are connected respectively with the first and second address inputs of the logical vector memory block, mode input the first and second blocks for storing and comparing associative signs and the write-read input of the logical vector memory block are the first, second, and third inputs of the device mode settings, and the fourth, fifth, sixth device mode inputs are respectively connected to three inputs of the operation unit operation codes, the first output of which is the first output of the device, the first input of the initial installation of the device is connected to the input of the initial installation of the operating unit, the second input of the initial set new - to the inputs of the initial installation of the first and second blocks of storage and comparison of associative signs, the first and second outputs of the logical vector memory block are connected respectively to the first and second information inputs of the operating unit, a single-bit output of the operating unit, which is the second output of the operating unit, characterized in that a block for the parallel search of a composite sample is introduced, having four inputs and one output, and the first input of the initial installation of the device is connected to the first input of block p arallle

Description

The utility model relates to the field of computer technology, can be used in information retrieval, expert systems of a production type, in automated control systems for technical objects, in specialized devices and systems for processing bit-byte information, etc.

Known parallel information retrieval system [Patent 2195015 of the Russian Federation, IPC G06F 17/30. Parallel system of information retrieval / V.M. Dovgal, S.S. Shevelev; applicant and patent holder Kursk, state. tech. un-t - No. 2001120172/09: declared 07/18/2001; publ. 12/20/2002, Bull. No. 12], which contains an occurrence memory block, a word memory block, a control block, an array of occurrence determination blocks that work simultaneously and incorporate a shift register for storing text and associative memory for storing a substring of a sample. The operation of the system consists in parallel matching in the associative memory of the substring of the pattern and the text. If there is no occurrence, the text is shifted by one position and a new iteration of the search. The disadvantage of this system is the inability to take into account structural relations of ordering occurrences of substrings of a composite sample in the analyzed text.

A device for parallel search and data processing [Patent 72771 Russian Federation, IPC G06F 12/00. Device for parallel search and data processing / E.A. Titenko, L.A. Lisitsin, V.M. Dovgal; applicant and patent holder Kursk, state. tech. un-t - No. 2007149075/22: declared 12/25/2007; publ. 04/27/2008, Bull. No. 12.], Which consists of two blocks for storing and comparing associative features, a logical vector memory block, an operation block, and a matrix search block that performs parallel processing of a set of characteristic vectors combined into a two-dimensional search matrix. The disadvantage of this device is its limited functionality - the device allows you to only search for occurrences of a sample consisting of only one substring. The characteristic search matrix has the geometric shape of a parallelogram, and the connections between adjacent elements of the diagonals are local in nature, which does not allow this device to solve the problem of searching for a composite sample in the analyzed sequence.

The prototype device is a Method and device for searching for a composite sample in a sequence / A.G. Kurochkin [et al.]; applicant and patent holder of South-West. state un-t July 15, 2013 No. 201132666/08 (048862)], consisting of a block for storing and comparing associative signs, a memory block of logical vectors, an operation block, a block for searching a composite sample, including, among other things, a characteristic matrix and sequentially calculating the starting cell values characteristic matrix within the row through a system of series-connected two-input elements OR.

An object of the invention is to increase the operating speed of the device due to the parallel calculation of the starting values of the cells of the characteristic matrix within the row. The essence of the invention consists in replacing a system of serially connected two-input OR elements within a row with a system of 2, 2, 3, ... k input OR elements providing parallel calculation of the starting values of cells within a row.

The solution to the technical problem is achieved by the fact that in the device for parallel search of a composite sample containing the first and second blocks for storing and comparing associative signs, a memory block of logical vectors and an operation block, the information inputs of the first and second blocks for storing and comparing associative signs are the first and second, respectively information inputs of the device, and the outputs of the blocks for storing and comparing associative signs are connected respectively with the first and second address inputs of the block the memory of logical vectors, the inputs of the job modes of the first and second blocks of storage and comparison of associative signs, and the write-read input of the memory block of the logic vectors are the first, second, and third inputs of the job of the device modes, and the fourth, fifth, sixth inputs of the job of the device modes are respectively three inputs of operation unit operation codes, the first output of which is the first output of the device, the first input of the initial installation of the device is connected to the input of the initial installation ki of the operating unit, the second input of the initial installation - to the inputs of the initial installation of the first and second blocks for storing and comparing associative signs, the first and second outputs of the logical vector memory block are connected respectively to the first and second information inputs of the operating unit, a single-bit output of the operating unit, which is the second the output of the operating unit, introduced a parallel search unit for a composite sample having four inputs and one output, the first input of the initial installation of the device the first input of the parallel search unit of the composite sample, the second input of which is connected to the second output of the operating unit, the third and fourth inputs of the parallel search unit of the composite sample are the third and fourth information inputs of the device, and the output of the parallel search unit of the composite sample is the second output of the device, wherein the parallel search unit of the composite sample contains a delay element, n registers for storing the codes of the characters of the composite sample with a capacity of p bits each, m registers for storing text character codes with bits of p bits each, k position triggers, as well as a characteristic matrix consisting of search cells and having a parallelogram geometric shape, matrix size - n × k search cells (k = m-n + 1 - the number of diagonals in the matrix) and (n-1) blocks of multi-input elements OR for parallel line-by-line calculation of starting values, with each register for storing symbol codes of a composite sample and each register for storing text symbol codes (first and second control inputs and third information p-bit input) and one p-bit output, each position trigger has three inputs (first and second control inputs and third information input) and one p-bit output, each search cell it has three information inputs (the first and second inputs are of a bit size each bit, the third is a one-bit input) and one output, each search cell contains a two-input comparison circuit for the equality of p-bit codes of characters of a composite sample and text and a two-input e element I, and the first and second p-bit inputs of the search cell are connected respectively to the first and second p-bit inputs of the two-input comparison circuit, respectively, the output of which is the first input of the two-input element And, the output of which is the output of the search cell, the second input of the two-input element And connected to the third input of the search cell, and the first p-bit inputs of all search cells of the i-th row of the matrix (i = 1-n) are connected to the p-bit output of the i-th register to store the character of the composite sample AZ, the p-bit output of the j-th register for storing the text character code (j = 1-m) is connected respectively to the second p-bit inputs of all the search cells included in the j-th column of the matrix, the outputs of the search cells of the i-th row, except i = n (the last row of the matrix), connected to the z-th inputs (z = 2-k) of the block of multi-input elements OR, the t-th outputs (t = 1-k) of which are connected to the third inputs of the search cells (i + 1 ) th row, except for i = n, to the first input of the block of multi-input elements OR in each row of the matrix, the value is a logical "0", the output of the search cell, p located in the last row of the matrix, connected to the third input of the j-th position trigger, the logical “1” value is applied to the third input of each search cell located in the first row of the matrix, the first input of the parallel search block of the composite sample is connected respectively to the first inputs of n registers for storing codes of characters of a composite sample, as well as with the first inputs of m registers for storing codes of characters of text and the first inputs of k triggers of positions, the second input is “Recording strings” of the parallel search block of a composite image a is connected to the input of the delay element and to the second inputs of n registers for storing codes of characters of the composite sample and the second inputs of m registers for storing codes of characters of the text, respectively, the output of the delay element is connected to the second inputs of k triggers of the positions, the outputs of which form the information k-bit output of the block parallel search for a composite sample, the third input of the parallel search block for a composite sample consists of n groups of p bits each group encoding the characters of the composite sample, and the i-th group of bits (i = 1-n) is fed to the third p-bit input of the i-th register for storing the code of the symbol of the composite sample, the fourth input of the parallel search block of the composite sample consists of m groups of bits of p bits each group encoding text characters, and j -th group of bits (j = 1-m) is fed to the third p-bit input of the j-th register to store the code of the text characters, each two-input equality comparison circuit in the search cell consists of a p-input element And, as well as p two-input elements of the sum modulo two with inversion i, the first inputs of which are supplied with the corresponding bit from the i-th p-bit group of the third input of the parallel search block of the composite sample, and the second inputs of two-input elements of the sum modulo two with inversion - the corresponding bit from the j-th p-bit group of the fourth input block parallel search for a composite sample, the outputs of all two-input elements of the sum modulo two with inversion are connected to the p-input element And, the output of which is a one-bit output of the two-input equality comparison circuit, the multi-input block ovyh OR elements having a k + 1 input and outputs k, k consisting of OR elements: a first two-input OR gate, the second two-input OR gate, a third OR gate trehvhodovogo, z-th input elements z-OR, etc. k-th k-input element OR.

In the i-th line, in addition to i = n, the logical “0” value is supplied to the first input of the two-input OR, and the second input of the first two-input OR element is connected to the output of the first search cell of the i-th line. The output of the first two-input OR element is connected to the first input of the second two-input OR element and is the first output of the block of multi-input OR elements. The output of the first two-input OR element is also connected to the 2nd, 3rd, etc. k-1st inputs of the third, fourth, etc. kth element OR.

In the i-th row, in addition to i = n, the z-th input of the z-th OR element (z = 2-k) is connected to the output of the z-th search cell of the i-th row. The output of the rth OR element is connected to the first input of the r + 1th OR element and is the rth output of the block of multi-input OR elements (r = 2-k-1). The output of the kth OR element is the kth output of the block of multi-input OR elements. The output of the t-th OR element (t = 2-k-2) is connected to the t-th, t + 1-st, etc. k-2nd inputs of t + 2nd, t + 3rd, etc. kth element OR.

The essence of the utility model is illustrated by drawings, where in FIG. 1 is a functional diagram of a device for parallel search of a composite sample; FIG. 2 is a functional block diagram of a parallel search for a composite sample, in FIG. 3 is a functional diagram of a search cell of a characteristic matrix, FIG. 4 is a functional block diagram of a multi-input OR element.

The parallel search device for a composite sample (Fig. 1) contains blocks 1 ₁ and 1 ₂ for storing and comparing associative features, a logical vector memory block 2, an operation block 3, a parallel composite search block 4, information inputs 4 ₁ , 4 ₂ , 4 ₃ and 4 ₄ , information outputs 5 ₁ -5 ₂ , inputs 6 ₁ -6 _{6 of} setting the operating mode, inputs 7 ₁ and 7 _{2 of the} initial installation.

The structure of blocks 1 ₁ , 1 ₂ , 2, 3 strictly corresponds to the prototype device in a circuit and in functional terms, consists of matching elements and the connections between them.

Block 4 for parallel search of a composite sample contains two control inputs: “Initial installation” 7 ₁ (first input) and input “Record strings” (second input), third and fourth inputs for supplying characters of a composite sample and text in parallel code through information inputs 4 ₃ and 4 ₄ devices, as well as one information output, which is the second output 5 ₂ device. In this case, the second control input of unit 4 is connected to the second output of the operation unit 3.

Block 4 of the parallel search of a composite sample contains a delay element 31, consisting of n pairs of inverters, n registers 32 ₁ -32 _n for storing the character codes of the composite sample, m registers 33 ₁ -33 _m for storing the character codes of the text, the characteristic matrix of the search cells 34 ₁₁ -34 _nm, and (n-1) multi-way elements 40 OR for parallel line-by-line calculation of starting values, k triggers of 37 positions, with register 32 _i (i = 1-n) and register 33 _j (j = 1-m) and the second control inputs, the third p-bit information input and one output, respectively but. The first and second inputs of n registers 32 for storing codes of characters of a composite sample and the first and second inputs of m registers 33 for storing codes of characters of text are connected respectively to the first and second control inputs of a block 4 for parallel search of a composite sample, the third input of which is p × n bit wide for parallel recording of a composite sample in registers 32 ₁ -32 _n and consists of n groups of bits of p bits each group encoding the characters of the composite sample, and the i-th group of bits (i = 1-n) is fed to the third p-bit in register 32 _i (i = 1-n), the fourth input of block 4 of parallel search for a composite sample with a bit size of p × m bits is intended for parallel text writing in registers 33 ₁ -33 _m and consists of m groups of bits of p bits each group encoding characters of the text, and the j-th group of bits (j = 1-m) is fed to the third p-bit input of the register 33 _j (j = 1-m). The second control input of the composite search parallel block 4 is also connected to the input of the delay element 31.

The characteristic matrix of search cells 34 ₁₁ -34 _nm has a size n × k cells (k = m-n + 1 is the number of diagonals in the matrix), and each search cell 34 _ij has three inputs and one output and contains a two-input comparison circuit 35 _ij for equality of p-bit character codes of a composite sample and text and a two-input element 36 I, each two-input equality comparison circuit 35 _ij in the search cell 34 _ij consists of a p-input element 39 I, as well as p two-input elements 38 ₁ -38 _p sum modulo two with inversion, the first inputs of which are fed respectively there is a discharge from the i-th p-bit group of the third input of block 4 of the parallel search for a composite sample, and the second inputs of two-input elements 38 ₁ -38 _p sum modulo two with inversion - the corresponding bit from the j-th p-bit group of the fourth block input 4 parallel search for a composite sample, all outputs of two-input elements 38 ₁ -38 _p sum modulo two with inversion in the two-input comparison circuit 35 _ij for equality are connected to the p-input element 39 AND, the output of which is the output of the two-input comparison circuit 35 _ij to in. The first and second p-bit inputs of the search cell 34 _{ij are} respectively connected to the first and second p-bit inputs of the two-input equality comparison circuit 35 _ij , the output of which is the first input of the two-input element 36 AND, the second input of which is the third input of the search cell 34 _ij , the output of which is the output of the two-input element 36 I.

The characteristic matrix of search cells 34 ₁₁ -34 _nm has a geometric parallelogram shape, in which each row contains k search cells shifted 1 position to the right from the next row of cells, starting from the cells of the first row 34 ₁₁ -34 _1k . This form of the matrix provides the direction of the search along the diagonals passing through the cells from the first row to the last row inclusive. Also, each row of the characteristic matrix, except for the last row, includes a block of multi-input OR elements, having k + 1 input and k outputs, consisting of k elements 41 OR: the first two-input element 41 ₁ OR, the second two-input element 41 ₂ OR, the third three-input element _{3 3} OR, z-th z-input element 41 _z OR, etc. k-th k-input element 41 _k OR, providing parallelization of the calculation of the starting values of the cells within the row.

In the i-th line, in addition to i = n, a logical “0” value is supplied to the first input of the two-input 41 ₁ OR, and the second input of the first two-input element 41 ₁ OR is connected to the output of the first search cell 34 _{1 of the} i-th line. The output of the first two-input element 41 ₁ OR is connected to the first input of the second two-input element 41 ₂ OR and is the first output of the block 40 of multi-input elements OR. The output of the first two-input element 41 ₁ OR is connected to the 2nd, 3rd, etc. k-1st inputs of the third, fourth, etc. of the kth element 41 OR.

In the i-th row, in addition to i = n, the z-th input of the z-th element 41 _z OR (z = 2-k) is connected to the output of the z-th search cell 34 _{z of the} i-th row. The output of the rth OR element 41 _r OR is connected to the first input of the r + 1th element 41 _{r + 1} OR and is the rth output of the block 40 of multi-input OR elements (r = 2-k-1). The output of the kth OR element 41 _k is the kth output of the block of multi-input OR elements 40. The output of the t-th element 41 _t OR (t = 2-k-2), connected to the t-th, t + 1-st, etc. k-2nd inputs of t + 2nd, t + 3rd, etc. of the kth element 41 OR.

The output of the search cell located in the last row of the matrix is connected to the third input of the j-th position trigger. On the third input of each cell located in the first row of the matrix, a logical value of “1” is supplied, thereby setting the direction of the search along the corresponding diagonal from the first row of the matrix to the last row inclusive.

The trigger 37 ₁ -37 _k positions store the search result in the form of a k-bit code, in which the logical “1” value marks the position of the beginning of occurrences of the composite pattern in the text. The trigger 37 _i position (i = 1-k) contains three inputs (first and second control, the third one-bit information input) and one output. The first input of the block 4 for parallel search of a composite sample is connected respectively to the first inputs of k triggers 37 positions, the second inputs of k triggers 37 positions are connected to the output of the delay element 31. The outputs of the triggers 37 ₁ -37 _k positions form a k-bit information output of block 4 of the parallel search for a composite sample.

This device, like the prototype device, works in the “Record” and “Operation” modes. The Record mode strictly corresponds to the algorithm described in the prototype device.

In the algorithm of the "Operation" mode, in addition to the operations performed in the prototype device, an operation is designated, designated as "PSO" and having its own operation code, which is supplied to the corresponding input of the operation mode.

Let the device perform the "Operation" mode with the operation code "PSO". Input 7 ₁ “Initial installation” of the operation unit 3 and unit 4 of the parallel search for a composite sample is supplied with a pulse signal of the initial installation, which resets register 22 of the commands at its input 1, register 30 at its input 1, and also k triggers 37 positions upon entry 1, n of registers 32 at their entry 1 and m registers 33 to their entry 1. After expiry of the initial setup signal to the input of _June 6th mode of the operation unit 3 is fed opcode "PCP", which is detected by decoder 23 and commands with second output opera ion unit 3 to the second input "Recording lines" parallel search unit 4 of the composite sample is supplied the pulse signal. This pulse signal at the “Record strings” input of the block 4 for parallel search of a composite sample is supplied respectively to the second inputs of the write permission of n registers 32 for storing codes of characters of the composite sample and to the second inputs of the write permission of m registers 33 to store codes of text characters, thereby n characters of the composite sample and m characters of the text in parallel code from the inputs 4 ₃ and 4 _{4 of the} device. Also, the pulse signal at the input "Record lines" of block 4 of the parallel search for a composite sample through the delay element 31 is supplied respectively to the second recording permission inputs of k triggers 37 positions. The delay element 31, made in the form of n pairs of inverters, is necessary to complete the search for a composite sample along the diagonals of the characteristic matrix, consisting of search cells 34 ₁₁ -34 _nm . The search begins with the cells of the first row of the characteristic matrix. The initial k-bit characteristic vector, equal to 11 ... 1, is fed to the third inputs of the search cells of the first row of the matrix and thereby determines the direction of parallel search on all diagonals of the characteristic matrix from the search cells of the first row to the search cells of the last row, inclusive. The calculation time of the starting points is reduced to k / 2τ _OR , where τ _OR is the delay time on the element 41 OR. Upon completion of the search processes, the pulse signal from the output of the delay element 31 after a time T ′ = m2τ _inv (2τ _inv is the delay time on the inverter chain) records the k-bit search result of the composite sample in the trigger 37 ₁ -37 _k positions. The outputs of the triggers 37 ₁ -37 _k positions are the k-bit output of the block 4 parallel search for a composite sample and form the second output of the device 5 ₂ .

The execution of the algorithm in the "Operation" mode on the remaining operations strictly corresponds to the prototype device.

Thus, an increase in the operating speed of the device is achieved by parallel calculation of the starting values of the cells of the characteristic matrix within the row based on the block of multi-input elements OR the number of k elements (2, 2, 3, ... k-input elements OR as part of a block of multi-input elements).

Claims (1)

A device for parallel search of a composite sample containing the first and second blocks for storing and comparing associative signs, a logical vector memory block and an operation block, the information inputs of the first and second blocks for storing and comparing associative signs are the first and second information inputs of the device, and the outputs of the storage blocks and comparisons of associative features are connected respectively with the first and second address inputs of the logical vector memory block, mode input the first and second blocks for storing and comparing associative signs and the write-read input of the logical vector memory block are the first, second, and third inputs of the device mode settings, and the fourth, fifth, sixth device mode inputs are respectively connected to three inputs of the operation unit operation codes, the first output of which is the first output of the device, the first input of the initial installation of the device is connected to the input of the initial installation of the operating unit, the second input of the initial set new - to the inputs of the initial installation of the first and second blocks of storage and comparison of associative signs, the first and second outputs of the logical vector memory block are connected respectively to the first and second information inputs of the operating unit, a single-bit output of the operating unit, which is the second output of the operating unit, characterized in that a block for the parallel search of a composite sample is introduced, having four inputs and one output, and the first input of the initial installation of the device is connected to the first input of block p parallel search of a composite sample, the second input of which is connected to the second output of the operating unit, the third and fourth inputs of the parallel search block of the composite sample are the third and fourth information inputs of the device, and the output of the parallel search block of the composite sample is the second output of the device, while the parallel search block the composite sample contains a delay element, n registers for storing the character codes of the composite sample with a bit length of p bits each, m registers for storing codes of text characters with p bits each, k position triggers, as well as a characteristic matrix consisting of search cells and having a parallelogram geometric shape, matrix size is n × k search cells, where k = m-n + 1 is the number of diagonals in the matrix , and (n-1) blocks of multi-input elements OR for parallel line-by-line calculation of starting values, in this case, each register for storing character codes of a composite sample and each register for storing text character codes have three inputs, respectively, the first and second control inputs and the third information p-bit input, and one p-bit output, each position trigger has three inputs, respectively - the first and second control inputs and the third information input, and one p-bit output, each search cell has three information inputs - the first and second inputs with a bit capacity of p bits each, the third - a single-bit input, and one output, each search cell contains a two-input comparison scheme for the equality of p-bit character codes of a composite sample and text and a two-input element And, moreover, the first and second p-bit inputs of the search cell are connected respectively to the first and second p-bit inputs of the two-input comparison circuit for equality, the output of which is the first input of the two-input element And, the output of which is the output of the search cell, the second input of the two-input element And is connected to the third input of the search cell, and the first p-bit inputs of all search cells of the i-th row of the matrix, where i = 1-n,  connected to the p-bit output of the i-th register for storing the symbol of the composite sample, p-bit output of the j-th register for storing the code of the text symbol, where j = 1-m, connected respectively to the second p-bit inputs of all the search cells included in the j-th column of the matrix, the outputs of the search cells of the i-th row, except i = n, the last row of the matrix, connected to the zth inputs, where z = 2-k, block of multi-input elements OR, t-th outputs, where t = 1-k,  which are connected to the third inputs of the search cells of the (i + 1) -th row, except for i = n, to the first input of a block of multi-input elements OR in each row of the matrix, the value is a logical "0", the output of the search cell located in the last row of the matrix is connected to the third input of the j-th position trigger, on the third input of each search cell located in the first row of the matrix, the value of the logical "1", the first input of the parallel search block of the composite sample is connected respectively to the first inputs of n registers for storing the character codes of the composite sample, as well as the first inputs of m registers for storing the character codes of the text and the first inputs of k position triggers, the second input "Recording strings" of the parallel search unit of the composite sample is connected to the input of the delay element and to the second inputs of n registers for storing the codes of characters of the composite sample and the second inputs of m registers for storing codes of the text characters, respectively, the output of the delay element is connected to the second inputs of k position triggers, the outputs of which form the information k-bit output of the parallel search unit of the composite sample, the third input of the parallel search block of a composite sample consists of n groups of p bits each group encoding the characters of a composite sample, moreover, the i-th group of bits, where i = 1-n, is fed to the third p-bit input of the i-th register to store the symbol code of the composite sample, the fourth input of the parallel search block of the composite sample consists of m groups of bits, p bits each group encoding characters of the text, moreover, the j-th group of bits, where j = 1-m, is fed to the third p-bit input of the j-th register to store the code of the text characters, each two-input equality comparison scheme in the search cell consists of a p-input element And, as well as p two-input elements, the sums are modulo two with inversion, the first inputs of which are supplied with the corresponding bit from the ith p-bit group of the third input of the parallel block search for a composite sample, and the second inputs of two-input elements of the sum modulo two with inversion - the corresponding bit from the j-th p-bit group of the fourth input of the parallel search block of the composite sample, the outputs of all two-input elements of the sum modulo two with inversion are connected to the p-input element And, the output of which is a one-bit output of the two-input comparison circuit to equality, a block of multi-input OR elements having k + 1 input and k outputs consisting of k OR elements: the first two-input OR element, the second two-input OR element, the third three-input OR element, the z-th z-input OR element, ..., along the k-th k-input element OR, in the i-th line, in addition to i = n, the logical “0” value is supplied to the first input of the two-input OR, and the second input of the first two-input OR element is connected to the output of the first search cell of the i-th line, the output of the first two-input OR element is connected to the first input of the second two-input OR element and is the first output of the block of multi-input OR elements, the output of the first two-input OR element is also connected to the 2nd, 3rd, ..., along the k-1st inputs of the third, fourth, ..., along the k-th OR elements, in the i-th row, in addition to i = n, the z-th input of the z-th OR element, where z = 2-k, is connected to the output of the z-th search cell of the i-th row, the output of the rth OR element is connected to the first input of the r + 1th OR element and is the rth output of the block of multi-input OR elements, where r = 2-k-1, the output of the kth OR element is the kth output of the block of multi-input OR elements, the output of the t-th OR element, where t = 2-k-2, is connected to the t-th, t + 1-m, ..., along the k-2-m inputs of t + 2-th, t + 3-th, ... , by the kth element OR.

Images