JPH0628205A - Majority decision making circuit - Google Patents

Abstract

PURPOSE:To reduce the circuit scale of the majority decision making circuit which generates one data frame by making a majority decision among corresponding bits of plural data frames having the same contents. CONSTITUTION:When a (j)th bits Dmj of (m)th data frames is added to a logical operation circuit 32, the circuit 32 finds the majority decision value Amj of (j)th bits up to the reception of the (m)th data frames and a value Cmj which is a half as large as the difference between '0' and '1' of (j)th bits up to the reception of the (m)th data frames from the value of the (j)th bit Dmj, the majority decision value A(m-1)j of (j)th bits up to a (m-1)th data frames outputted from a main buffer 21, a value C(m-1)j which is a half as large as the difference between '0' and '1' of (j)th bits up to the (m-1)th data frames outputted from counter buffers 22-1-22(N-1), and the order of the (m)th data frames, and stores the found majority decision value Amj and value Cmj in the main buffer 21 and counter buffers 22-1-22-(N-1).

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a majority decision circuit, and in particular, it receives a plurality of data of the same contents sent from a transmitting side and takes a majority decision between corresponding bits of each received data to obtain a received data. The present invention relates to a majority decision circuit that determines the value of each bit of.

[0002]

2. Description of the Related Art In a car telephone, in order to reduce data transmission / reception errors, a data frame having the same content (including data and control data) is controlled 5 times or 11 times before and after the data transmission. Send with a frame,
At the time of receiving data, the majority of the corresponding bits of the data included in the data frame for 5 or 11 times is majority-determined to generate the received data.

FIG. 9 is a block diagram showing an example of a majority decision circuit which has been conventionally used in the above-mentioned case. It has a data input terminal 11, a majority decision output terminal 12, and M buffers 41-1 to 41. -M, a control circuit 51, and a logical operation circuit 52. The buffer 41-
The number of 1 to 41-M is the same value as the number of repetitions of the data frame having the same content.

The control circuit 51 has a data input terminal 11 having a first
When the th to M th data frames are added, the first
The data (excluding control data) included in the 1st to Mth data frames are respectively buffers 41-1 to 4-4.
Store in 1-M.

When the data in the last data frame, that is, the Mth data frame is stored in the buffer 41-M, the control circuit 51 causes the first bit of the data stored in each of the buffers 41-1 to 41-M. The logical operation circuit 52
Add to.

The logical operation circuit 52 takes the majority decision of the added M values and outputs the result to the majority decision output terminal 12 as the value of the first bit of the received data.

After that, the control circuit 51 causes the buffer 41-1 to operate.
The second bit of the data stored in 41 to M is added to the logical operation circuit 52. As a result, the logical operation circuit 5
Similarly to the above, 2 takes the majority decision of the M values and outputs the result to the majority decision output terminal 12 as the value of the second bit of the received data.

Thereafter, the same operation as described above is repeated until the final bit of the data to generate the received data. If it is necessary to parallelize the majority value of each bit output from the majority output terminal 12 by the CPU, the serial data output to the majority output terminal 12 should be taken out as parallel data. It is necessary to connect a buffer (not shown) capable of performing the above.

Now, for example, the data applied to the data input terminal 11 is, as shown in FIG.
67 and five data frames 61 to 65 of the same content sandwiched between them, the buffer 4 required
The number M of 1-1 to 41-M is 5. If each of the data frames 61 to 65 is composed of 80-bit data and control data, the required capacity of each of the buffers 41-1 to 41-5 is 80 bits.

[0010]

As described above, the conventional majority circuit carries out the majority decision after receiving all the M data frames having the same contents, and it is possible to store the M data frames. Since it is necessary, (number of bits of data in data frame) × (number of data frames) buffer flip-flops are required. In the example of FIG. 10, since the data frame length is 80 bits and the number of data frames is 5, the number of buffer flip-flops required is 400. Generally, a flip-flop has a large number of transistors of 20 to 30. Therefore, if a conventional majority circuit is to be integrated into an IC, about 10,000 transistors are needed only for a buffer, and the circuit scale is large. It has the drawback of becoming large.

An object of the present invention is to provide a majority circuit which can reduce the circuit scale.

[0012]

In order to achieve the above object, the present invention receives a plurality of data frames of the same content repeatedly transmitted from a transmitting side, and performs a majority operation between corresponding bits of each received data frame. In the majority circuit for generating one result data frame in which each bit has the value of the majority operation result, a main buffer, a counter buffer that constitutes a numeral part by bits at respective corresponding positions, and The majority value stored in the main buffer until the reception of the previous data frame, and "0" and "1" of each bit stored in each digit part of the counter buffer until the reception of the previous data frame. The value of 1/2 of the difference between the number of and the received data frame, the content of the data frame received this time, and the order of the data frame currently received To obtain the majority value up to the data frame and the half of the difference between the number of “0” and “1” of each bit up to the currently received data frame, and the obtained majority value is stored in the main buffer. A logical operation circuit is provided which stores the value of 1/2 of the difference between the stored and obtained "0" and "1" of each bit in the corresponding numeral part of the counter buffer. .

[0013]

When the new data frame is received, the logical operation circuit stores the majority value stored in the main buffer until the reception of the previous data frame, and the previous data frame stored in each digit part of the counter buffer. Based on the half value of the difference between the number of “0” and “1” of each bit until reception, the content of the data frame currently received, and the order of the data frame currently received. Then, a half value of the majority value up to the data frame currently received and the difference between the numbers of “0” and “1” of each bit up to the data frame currently received is calculated.

Then, the obtained majority decision value is stored in the main buffer, and the difference between the obtained numbers "0" and "1" of each bit is 1
The value of / 2 is stored in the corresponding digit part of the counter buffer. Therefore, each time a new data frame is received,
The latest majority value is stored in the main buffer, and the latest "0" and "1" of each bit are stored in each digit of the counter buffer.
A half value of the difference between the numbers of and is stored.

[0015]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of the present invention, in which a data input terminal 11, a majority output terminal 12, and 1
It is composed of a plurality of main buffers 21, (N-1) counter buffers 22-1 to 22- (N-1), a control circuit 31, and a logical operation circuit 32.

To the data input terminal 11, the first to Mth data frames (including data and control data) of the same content repeatedly sent from the transmitting side and the control frames sandwiching the same are input. Incidentally, in this embodiment,
The data D1 to D1 in the first to Mth data frames
It is assumed that the DM has J bits as shown in FIG. Further, in this embodiment, the j-th bit (1 ≦ j ≦) of the data Dm in the m-th (1 ≦ m ≦ M) data frame.
J) Let the eyes be represented by Dmj.

In the logical operation circuit 32, the j-th bit Dmj of the data Dm is added via the data input terminal 11, so that the j-th bit of the data D1, D2, ..., Dm received so far to the main buffer 21. Bit majority decision Am
, a function of outputting j (majority decision value of D1j, D2j, ..., Dmj) and counter buffers 22-1 to 22- (N-
Data D1, D2 input so far for 1)
, 1 of the difference between the number "1" and "0" of the j-th bit of Dm
A count value Cm of (N-1) -bit configuration indicating a value of / 2
and a function of outputting j (bit1 to bitN-1).

As shown in FIG. 3, the main buffer 21 is composed of a J-bit shift register, and every time the majority operation value of each bit is output from the logical operation circuit 32, the bits AJ ... The contents of A1 are shifted to the right, and the majority value output from the logical operation circuit 32 is fetched in the Jth bit AJ. Therefore, at the time when the logical operation circuit 32 completes the processing for the Jth bit DmJ of the data Dm and outputs the majority decision value AmJ, the contents of the respective bits A1 to AJ of the main buffer 21 are as shown in FIG. Become. In FIG. 4, Amj is the data D1,
The majority value of the j-th bit of D2, ..., Dm is represented.

Counter buffers 22-1 to 22- (N-
1) each comprises a J-bit configuration shift register as shown in FIG.
-1 to 22- (N-1) corresponding bits B1j, B2
.., B (N-1) j constitutes a numeral part Cj of the counter having a (N-1) -bit configuration. That is, the corresponding bits of each of the counter buffers 22-1 to 22- (N-1) form the number units C1 to CJ of the counter having J (N-1) bits.

Then, each counter buffer 22-1 to 2-2
2- (N-1) is "0" and "1" from the logical operation circuit 32.
Every time a count value having a (N-1) -bit configuration showing a value of 1/2 of the difference between the numbers of (1) and (2) is output, the contents of the Jth bit to the 1st bit are shifted to the right under the control of the control circuit 31. , The count value output from the logical operation circuit 32
Take in a bit. Therefore, the logical operation circuit 32 completes the process for the J-th bit DmJ of the data Dm, and (N-
1) Count value CmJ (bit1 to bit) of bit configuration
When N-1) is output, the contents of counter buffers 22-1 to 22- (N-1) are as shown in FIG. That is, the logical operation circuit 32 completes the process for the Jth bit DmJ of the data Dm, and the count value CmJ (b
bit j of the counter buffers 22-1 to 22- (N-1) at the time of outputting it1 to bitN-1)
The values of nj are Cmj (bit1) to Cmj (bitN-
It becomes 1).

Next, the operation of this embodiment will be described.

First, the operation when the data D1 in the first data frame is applied to the data input terminal 11 will be described.

The logical operation circuit 32 receives each bit D11, D12, ..., D1 of the data D1 via the data input terminal 11.
When the value of J is added, the majority decision values A11, A of each bit
12, ..., A1J are sequentially output. In this case, it is the first data frame, and each bit D11, D12,
,, the value of D1J is the majority decision value A11, A12,
, A1J, the logical operation circuit 32 sets each bit D
The values of 11, D12, ..., D1J are converted into majority values A11, A1.
, ..., A1J is output.

The main buffer 21 sequentially shifts the majority decision values A11, A12, ..., A1J output from the logical operation circuit 32 under the control of the control circuit 31. FIG. 7 is a diagram showing a state in which the majority voting values A11, A12, ..., A1J are shifted in the main buffer 21, and at the time when the logical operation circuit 32 inputs the data D1J and outputs the majority voting value A1J. Are bits A1, A2, ..., Of the main buffer 21.
The contents of AJ are the majority decision values A11, A12, ..., A, respectively.
It will be 1J. In addition, in FIG. 7, X indicates an indefinite value.

Further, the logical operation circuit 32 inputs the data D1 in the first data frame via the data input terminal 11.
Is added, the counter buffers 22-1 to 22-
The count value of (N-1) is cleared, and the numeral parts C1 to Cj
All values of 0. That is, when the data D1 in the first data frame is received, the corresponding bit “0” is received.
This is because the difference between the numbers of "1" and "1" is 1, and the value obtained by halving it (the value shifted right by 1 bit) becomes 0.

Next, the operation when the data in the second and subsequent data frames is added to the data input terminal 11 will be described.

When the data Dm in the m-th (m> 1) data frame is added to the logical operation circuit 32 via the data input terminal 11, each bit Dm1, Dm2, ..., D is added.
The following processing is performed on the main buffer 21 and the counter buffers 22-1 to 22- (N-1) for each mj, ..., DmJ.

First, the processing performed on the main buffer 21 will be described.

When the j-th bit Dmj of the data Dm is added via the data input terminal 11, the logical operation circuit 32 is output from the counter buffers 22-1 to 22- (N-1) (N-1). Count value C (m-
1) Whether or not the value of j (bit1 to bitN-1) is 0, that is, the data D1 to D (m input so far.
-1) 1 / the difference between the number of the j-th bit "0" and "1"
It is determined whether the value of 2 is 0.

Then, the count value C (m-1) j (bi
When it is determined that t1 to bitN-1) indicates 0, the logical operation circuit 32 outputs the value of the j-th bit Dmj of the input data Dm to the main buffer 21 as the j-th bit majority value Amj. . That is, the count value C (m-
1) When j (bit1 to bitN-1) indicates 0, the data D1 to D (m-1) input so far
The number difference between the j-th bit “0” and “1” is 0 or 1, and the value of the j-th bit Dmj becomes the majority value, or the number of “0” and “1” is the same number. Because it will be.

Further, the count value C (m-1) j (bit
1-bit N-1) does not indicate 0, the logical operation circuit 32 newly outputs the majority decision value A (m-1) j of the j-th bit output from the main buffer 21 so far. The majority decision value Amj is output to the main buffer 21. That is, the count value C (m-1) j (bit1 to bi
If tN-1) does not indicate 0, "0" of the j-th bit of the data D1 to D (m-1) input so far.
This is because the difference between the numbers of "1" and "1" is 2 or more, and the majority decision value does not change depending on the value of the j-th bit Dmj of the data Dm input this time.

The logical operation circuit 32 performs the same processing when another bit is added, and outputs the majority decision value for that bit to the main buffer 21. When the majority value is output from the logical operation circuit 32, the main buffer 21 shifts the content to the right by 1 bit and fetches the majority value into the Jth bit AJ, as described above.

Next, the counter buffers 22-1 to 22-
The processing performed for (N-1) will be described.

The logical operation circuit 32 recognizes whether the odd-numbered data frame is being received or the even-numbered data frame is being received, and is receiving the odd-numbered data frame and the even-numbered data frame. Different processing is performed on the counter buffers 22-1 to 22- (N-1).

When the odd-numbered data frame is received, the logical operation circuit 32 causes the j-th bit Dm of the data Dm.
j is added via the data input terminal 11, Dmj
It is determined whether or not ≠ A (m-1) j and C (m-1) j ≠ 0 (minimum value of the count values of the numeral units C1 to CJ).

Then, Dmj ≠ A (m-1) j,
When it is determined that C (m−1) j ≠ 0, that is, the value of the jth bit Dmj of the data Dm input this time and the majority decision value A (m−1) j of the jth bit so far are When it is determined that the count value C (m-1) j that is not equal to and is 1/2 of the difference between the numbers "0" and "1" of the j-th bit so far is not 0, The logical operation circuit 32 outputs the count value C (m-1) j (bit1 to bitN-) output from the counter buffers 22-1 to 22- (N-1).
A count value Cmj (bi showing a value obtained by subtracting 1 from 1)
t1 to bitN-1) to the counter buffers 22-1 to 22-2
Output to 2- (N-1).

If it is determined that it is not, the logical operation circuit 32 causes the counter buffers 22-1 to 22- (N
-1) count value C (m-1) j output from
The count value Cmj (bit1 to bitN-1) indicating the same value as (bit1 to bitN-1) is output to the counter buffers 22-1 to 22- (N-1).

When an even-numbered data frame is being received, the logical operation circuit 32 outputs D when the bit Dmj of the data Dm is added via the data input terminal 11.
mj = A (m-1) j and C (m-1) ≠ 2
It is determined whether or not it is ^N-1 -1 (the maximum value of the count values of the numeral units C1-CJ).

Then, Dmj = A (m-1) j,
And when it is determined that C (m-1) ≠ 2 ^N-1 -1,
That is, the value of the j-th bit Dmj of the data Dm input this time is equal to the majority decision value A (m-1) j of the j-th bit so far, and the "0" and "1" of the j-th bit so far. When it is determined that the difference in the number of the counters is not 2 ^N-1 -1, the count value C (m-1) j (bit1 to bitN) output from the counter buffers 22-1 to 22- (N-1). −
Count value Cmj indicating a value obtained by adding 1 to the value indicated by 1)
(Bit1 to bitN-1) is the counter buffer 22-
1 to 22- (N-1) are output.

When it is determined that it is not, the logical operation circuit 32 causes the counter buffers 22-1 to 22- (N-
1) The count value C (m-1) j (b output from 1)
count value Cm indicating the same value as it1 to bitN-1)
j (bit1 to bitN-1) to the counter buffer 22
It outputs to -1 to 22- (N-1).

If Dmj ≠ A (m−1) j, the difference between the numbers of “0” and “1” of the j-th bit is reduced by 1 even when an even-numbered data frame is received. The count value Cmj is set to be smaller than the count value C (m-1) j by 1 only when the odd-numbered data frame is received, because the count value Cmj indicates the difference in the number between "0" and "1". 1
This is because the value is / 2.

If Dmj = A (m-1) j,
Even when the odd-numbered data frame is received, the difference between the number of the j-th bit “1” and “0” is increased by 1, but only when the even-numbered data frame is received, the count value Cmj is changed to the count value C (m -1) One is larger than j because the count value Cmj is 1/2 the difference between "0" and "1".
It is because it is the value.

The logical operation circuit 32 performs the same processing as described above with respect to the other bits, and outputs the count value indicating the half of the difference between "0" and "1" of each bit to the counter buffer 22-. 1 to 22- (N-1) are output. The counter buffers 22-1 to 22- (N-1) add a count value indicating a half value of the difference between "0" and "1" from the logical operation circuit 32, and set the contents to 1 to the right. At the same time as bit shifting, the count value output from the logical operation circuit 32 is captured in the J-th bit that constitutes the numeral part CJ.

The logical operation circuit 32 repeats the same processing as described above up to the data DM in the last Mth data frame, and when the processing for the data DM is completed, the majority decision value AM1 stored in the main buffer 21. ，
AM2, ..., AMJ are sequentially output from the majority output terminal 12.

By the way, one main buffer 21 and (N
-1) counter buffers 22-1 to 22- (N-
In the majority circuit of this embodiment having 1), the maximum value of the count value that can be set in the register units C1 to CJ is the number of counter buffers 22-1 to 22- (N-1) ( Since it is N-1), it becomes 2 ^N-1 -1, but a half value of the difference between the numbers of "0" and "1" of the input data is written in the numeral parts C1 to CJ. Therefore, the registered parts C1 to CJ
The maximum value that can be expressed by is (2 ^N-1 -1) x 2 + 1 =
2 ^N -1.

That is, in the majority circuit of this embodiment, the difference between the numbers of "0" and "1" is 2 in order to obtain the correct majority value.
^The majority vote must be established before it exceeds ^N -1. The maximum value of the number of data frames satisfying this condition is (2 ^N −1) × 2-1 = 2 ^{N + 1} −3. That is, in the majority circuit of this embodiment, which has a total of N buffers including one main buffer 21 and (N-1) counter buffers 22-1 to 22- (N-1), a maximum of 2 ^{N is possible.} The majority of the data in the ⁺¹ -3 data frame can be taken. That is, when m is an odd number and m ≦ 2 ^{N + 1} −3, the data Dm
The value of Amj after receiving j always indicates the majority value.

Now, for example, the data applied to the data input terminal 11 is, as shown in FIG.
67 and five data frames 61 to 65 of the same content sandwiched between them, and if the data in each data frame 61 to 65 is 80 bits, the number of data frames M = 2 ^{N + 1} −3 = 5, the required number N of buffers is 2
Number (one each for main buffer and counter buffer)
Therefore, the required number of buffer flip-flops is 80
The number will be from 2 to 160 pieces. As described above, according to the present embodiment, the number of buffer flip-flops, which is 400 in the related art, can be significantly reduced.

Further, as shown in FIG. 8, the main buffer 21
Is configured by using a shift register or the like whose contents can be read in parallel, parallel data that can be processed by a CPU or the like can be obtained without connecting a buffer to the majority output terminal 12 as in the prior art. be able to.

[0050]

As described above, according to the present invention, the main buffer in which the majority value is stored until the latest data frame is received, and "0" and "1" of each bit until the latest data frame is received. Based on the contents of the main buffer, the counter buffer, the data frame newly received this time, and the order of the data frame newly received this time, It is provided with a logical operation circuit for storing in the main buffer and a counter buffer a value that is ½ of the difference between the numbers of “0” and “1” until the current data frame is received. As described above, since it is not necessary to store all the data frames sent from the transmitting side, the number of buffers required can be reduced. Therefore, according to the present invention, there is an effect that the circuit scale of the majority circuit can be reduced. In particular, since the number of buffers substantially follows the logarithmic value of the number of data frames, the larger the number of frames, the greater the effect.

[Brief description of drawings]

FIG. 1 is a block diagram of an embodiment of the present invention.

FIG. 2 is a diagram showing a configuration example of data input to a majority decision circuit.

FIG. 3 is a diagram showing a configuration example of a main buffer 21.

FIG. 4 is a diagram showing an example of contents of a main buffer 21.

FIG. 5 is a counter buffer 22-1 to 22- (N-1).
It is a figure which shows the structural example.

FIG. 6 is a counter buffer 22-1 to 22- (N-1).
It is a figure which shows the example of the content of.

FIG. 7 is a diagram showing how the main buffer 21 shifts a majority decision value.

FIG. 8 is a block diagram of another embodiment of the present invention.

FIG. 9 is a block diagram of a conventional example.

FIG. 10 is a diagram showing an example of received data.

[Explanation of symbols]

 11 ... Data input terminal 12 ... Majority output terminal 21 ... Main buffer 22-1 to 22- (N-1) ... Counter buffer 31, 51 ... Control circuit 32, 52 ... Logical operation circuit 41-1 to 41-M ... Buffer 61-65 ... Data frame 66, 67 ... Control frame

Claims (2)

[Claims] 1. A plurality of data frames having the same content, which are repeatedly transmitted from a transmitting side, are received, a majority operation is performed on corresponding bits of each received data frame, and each bit has a value of a majority operation result. In a majority circuit that generates two result data frames, a main buffer, a counter buffer that configures a digit part by bits at corresponding positions, and until the last data frame stored in the main buffer is received. And the half value of the difference between the number of “0” and “1” of each bit stored in each digit part of the counter buffer until the last data frame is received, Based on the content of the received data frame and the order of the currently received data frame, the majority value up to the currently received data frame and the currently received data frame are received. The half value of the difference between the number "0" and "1" of each bit up to the data frame, the obtained majority decision value is stored in the main buffer, and the obtained "0" of each bit And a logical operation circuit for storing a half value of the difference between the numbers of "1" and "1" in a corresponding numeral part in the counter buffer. 2. The logical operation circuit stores the content of the first data frame in the main buffer when receiving the first data frame, and
When the counter buffer is cleared and the second and subsequent data frames are received, of the bits of the main buffer, the value of the corresponding bit of which the value of the numeral part is 0 is With the value of the corresponding bit, when the second and subsequent odd-numbered data frames are received, the bit value of the corresponding main buffer among the respective digit parts corresponds to the bit of the data frame currently received. 1 is subtracted from the value of the register part different from the value of, and when the second and subsequent even-numbered data frames are received, the corresponding bit value of the main buffer among the register parts is received this time. 2. The majority decision circuit according to claim 1, wherein the value of the same numeral part as the value of the corresponding bit of the existing data frame is incremented by one.