JPH10163887A - Interleave device and deinterleave device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To improve the memory using efficiency and to always rearrange the data in the vertical direction from the horizontal direction in any frame by writing the data on a single symbol in an idle address that is acquired by reading the data on a single symbol out of a memory. SOLUTION: A binary counter 11 counts the symbols included in a frame and outputs this count value to a shift calculation means 12 as a 5-bit signal (a). The means 12 divides a shift number (b+2) by 5 to calculate the remainder and outputs this at the end of the frame as a new shift number (b). A cyclic shift means 13 outputs an address signal (c) that is obtained by shifting cyclically the signal (a) by the number (b). Then the data (tx) are repetitively written for each symbol in an idle address that is acquired by reading the data (itx) out of a memory 14. The read data are outputted as the interleave data. At an interleave part, the data are rearranged by the same rule for a fixed period based on the shift number increment (i) and regardless of the shift number (b).

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an interleave / deinterleave device used in a digital communication system or a digital recording system.

[0002]

2. Description of the Related Art In digital mobile communications, fluctuations in received power due to fading and the like cause continuous errors called burst errors. On the other hand, in a digital storage device using magnetic recording or the like, a physical defect such as a scratch on a recording medium causes a burst error. To cope with such a burst error, a method of interleaving error correction codes is often used. Interleaving is a process of rearranging the order of a data sequence.
First, a data sequence is interleaved before transmission or recording. Then, at the stage of reception or reproduction, the data sequence is returned to the original order by performing deinterleaving, which is the reverse process of interleaving. By this interleaving and deinterleaving processing, burst errors occurring on the transmission path or the recording medium are dispersed on the data sequence. Therefore, it is possible to correct a burst error having a length that cannot be corrected by the error correction code alone.

FIG. 2 shows one of the typical interleaving schemes.
Show one. The data sequence is interleaved by outputting the data sequence arranged in the horizontal direction on the mxn matrix in the vertical direction.

When a code can correct an arbitrary burst error of length t, and there is a burst error of length t + 1 that cannot be corrected, the burst error correction capability of the code is said to be t. Assuming that one frame is composed of m words of an error correction code and each word has a code length of n and a burst error correction capability of t, FIG. 3 shows how interleaving based on the method of FIG. 2 is performed. Since the generated burst error is evenly distributed to each word of the error correction code, it is possible to correct a burst error having a length of m × t.

FIG. 4 shows a block diagram of a conventional interleave device based on the system shown in FIG. The interleave device includes memories 41 and 42 for storing an m × n matrix data sequence, an address counter 43 for outputting a write address signal, and a read address signal obtained by exchanging upper and lower bits of the write address signal. Address conversion means 44 to output, and select either a write address signal or a read address signal,
Switches 45, 4 for outputting to memories 41, 42, respectively
6, a switch 47 for supplying an input data sequence to one of the memories 41 and 42, and a switch 48 for selecting and outputting a data sequence from the memories 41 and 42.

An m × n data sequence is defined as one frame.
First, the first frame is written into the memory 41. Next, while the first frame already written is read from the memory 41, the second frame is written to the memory 42. This time, the third frame is written to the memory 41 while the second frame already written is read from the memory 42. Thereafter, an operation in which writing is performed on one of the memories 41 and 42 and reading is performed on the other is alternately repeated.

The conventional apparatus shown in FIG. 4 faithfully implements the system shown in FIG. 2. When used together with an error correction code having a code length n and a burst error correction capability t, the burst error correction capability m × t
Can be obtained.

As shown in FIG. 5, there has also been proposed an apparatus in which the memory capacity is reduced to half that of the apparatus shown in FIG. 4 (Japanese Patent Application Laid-Open No. 62-200974). The device of FIG. 5 outputs a memory 51 for storing an m × n matrix data sequence, an address counter 52 for outputting an address signal adr1, and an address signal adr2 obtained by exchanging upper and lower bits of the address signal adr1. Address conversion means 53 and address signals adr1, ad
It comprises a switch 54 for selecting either one of r2 and outputting to the memory 51. The writing / reading operation of the data series is performed while the address signals adr1 and adr2 are alternately supplied to the memory 51 for each frame with the m × n data series as one frame. First, the address signal adr1 is supplied to the memory 51, and the first frame is written to the memory 51. Next, the address signal adr2
Is supplied to the memory 51, and the reading of the first frame and the writing of the second frame are performed simultaneously. That is, the operation of writing the symbols of the second frame to the free addresses generated by reading the symbols of the first frame is repeated one symbol at a time. This time, the address signal adr1 is supplied to the memory 51, and the reading of the second frame and the writing of the third frame are performed simultaneously by the same operation. Thereafter, the same operation is repeated while alternately switching the address signal.

An address signal adr1 is supplied to the memory 51.
Supplies addresses in the horizontal order shown in FIG.
On the other hand, the address signal adr2 supplies addresses in the vertical order shown in FIG. Therefore, the odd-numbered frames are written in the horizontal address order and read out in the vertical address order. Conversely, even-numbered frames
Writing is performed in the vertical address order, and reading is performed in the horizontal address order. Therefore, when m and n are different,
Data rearrangement rules are different between odd-numbered frames and even-numbered frames.

In the apparatus of FIG. 5, a memory of m × n = 4 × 8 is used, code length n = 8, burst error correction capability t =
FIG. 6 shows how one error correcting code is interleaved. At this time, one frame is composed of four words of the error correction code, and each word is composed of eight symbols. The burst error correction capability of the interleaved frame will be described below. In the odd-numbered frames, a burst error is allocated to each word one by one as shown in FIG. Since each word can correct t = 1 errors, the entire frame has a length m × t = 4
Burst error can be corrected (burst error correction capability: 4). But in the even frame,
As shown in FIG. 6B, each word is divided into two stages and arranged vertically. Therefore, since two burst errors are assigned to each word, a burst error having a length of 4 or less may not be corrected. For example, the length 2 shown in FIG.
Cannot be corrected, and it is always possible to correct the error up to a length of 1 (burst error correction capability:
1).

In addition to the apparatus shown in FIG. 5, address conversion means 53 is provided for the purpose of realizing a more general address conversion method.
Japanese Patent Application Laid-Open No. 59-19351 discloses a method using a ROM instead of
No. 3 proposes this. Japanese Patent Application Laid-Open No. 61-177 discloses a method in which the matrix of a data series is limited to the case where m = n.
No. 555 proposes.

[0012]

The conventional interleaver shown in FIG. 4 requires a memory capacity of two frames. The conventional interleave device shown in FIG. 5 has a required memory capacity of one frame, but since the data rearrangement rules are different for each frame, the original burst error correction capability by using the error correction code together is not sufficient. May not be able to demonstrate.

According to the present invention, there is provided an interleave device which uses only one memory for storing one frame of data and always rearranges data from the horizontal direction to the vertical direction for any frame based on the method shown in FIG. provide. A deinterleave device having the same circuit configuration as the interleave device and performing data rearrangement from the vertical direction to the horizontal direction by an independent operation is provided.

[0014]

In order to solve this problem, according to the present invention, one symbol data is read from a memory, and one symbol data is written to a free address generated, thereby improving the memory use efficiency. The output of the address counter is cyclically shifted and supplied to the memory, and the number of shifts is increased by a certain number for each frame, thereby realizing a certain sorting rule.

[0015]

BEST MODE FOR CARRYING OUT THE INVENTION

(Embodiment 1) Hereinafter, a first embodiment of an interleave / deinterleave device of the present invention will be described.

In this embodiment, i = 2 and j = 3, and FIG.
, A frame is composed of m = 2 ＾ i = 4 words, and a word is composed of n = 2 ＾ j = 8 symbols. However, in this specification, “＾” is used as a symbol representing a power.

FIG. 1 is a block diagram showing the configuration of the interleave / deinterleave device of the present embodiment. The interleave section includes a binary counter 11, shift number calculating means 12, cyclic shift means 13, and memory 14. On the other hand, the deinterleave unit includes a binary counter 15, a shift number calculating unit 16, and a cyclic shift unit 1.
7 and a memory 18.

The binary counter 11 counts symbols in the frame, and counts the counted value as a signal of k = i + j = 5 bits a = (a [4], a [3], a [2], a
[1], a [0]).

The shift number calculating means 12 sets the initial value of the shift number b to 0, and sets b + i = b + 2 to k =
The remainder divided by 5 is calculated, and the remainder is output as a new value of b until the end of the frame. The calculation result of the output value is shown in (Equation 1). However, in this specification, “mod” is used as a symbol representing a remainder. That is, “x mod y” represents a remainder when x is divided by y.

[0020]

(Equation 1)

Thereafter, the calculation of (Equation 1) is repeated. Note that the initial value of the shift number b may be any integer from 0 to 4, and need not necessarily be 0.

The cyclic shift means 13 cyclically shifts the output signal a of the binary counter by the shift number b to generate an address signal c = (a [b-1], a [b-
2],..., A [1], a [0], a [4],.
, A [b + 1], a [b]). The address signal c for the value of b is shown in (Equation 2).

[0023]

(Equation 2)

In equation (2), a series of count values a = 0, 1,
By substituting 2, 3,..., 31, a specific value of c is calculated. For example, when b = 1, the value of the address signal c is as shown in (Equation 3).

[0025]

(Equation 3)

The sequence of the address signal c with respect to the shift number b is represented by seq (b). For example, when b = 1, it becomes as shown in (Equation 4).

[0027]

(Equation 4)

Then, the address sequence is seq (0), s
eq (2), seq (4), seq (1), seq
(3), seq (0),... Are supplied to the memory 14 in this order. One address series is composed of 32 addresses, and a read / write operation is performed for each address. That is, the operation of writing the data tx to the empty address generated by reading the data itx from the memory 14 is repeated for each symbol. The read data is output as interleaved data.

The data rearrangement rule in the interleave section is uniquely determined by the shift number increment i regardless of the value of the shift number b. That is, as long as i is constant, data rearrangement is always performed according to the same rule for any frame. The rearrangement is equivalent to rearrangement from the horizontal direction to the vertical direction on the mxn matrix.

The configuration of the deinterleave section is the same as the configuration of the interleave section, but the value of the signal input to the shift number calculating means is different. While i = 2 is input to the interleave part, j =
3 is input. The output e of the shift number calculation means 16 is calculated as in (Equation 5), with the initial value being 0.

[0031]

(Equation 5)

Thereafter, the calculation of (Expression 5) is repeated. Note that an arbitrary integer from 0 to 4 can be used as the initial value of the shift number e, and it is not necessarily required to be 0.

The method of calculation in the cyclic shift means 17 is the same as that of the interleave unit, but the calculation results are different because the input shift numbers are different, and the order of the address series supplied to the memory 18 is seq (0), seq
(3), seq (1), seq (4), seq (2),
seq (0),...

The data rearrangement rule in the deinterleave section is such that, regardless of the value of the shift number e, the shift number increment j
Is uniquely determined by That is, as long as j is constant, data rearrangement is always performed on any frame according to the same rule. The rearrangement is equivalent to the rearrangement from the vertical direction to the horizontal direction on the mxn matrix.

FIG. 8 is a timing chart for each frame of each signal in the interleave / deinterleave device of this embodiment. a, b, c, d, e, and f show specific values of each signal in FIG. tx represents a frame sequence input to the interleave unit, and itx represents tx
Represents an output frame sequence obtained by interleaving. For example, t1 represents an input first frame, and it1 represents an output frame obtained by interleaving the first frame t1.
irx represents a frame sequence input to the deinterleave unit, and rx represents an output frame sequence obtained by deinterleaving irx. For example, ir1 represents an input first frame, and r1 represents an output frame obtained by deinterleaving ir1. The number of delay frames through input and output is 1 in both the interleave section and the deinterleave section.

In this embodiment, since the operation of the interleave unit and the operation of the deinterleave unit are completely independent, it is possible to separate and implement the device. For example, it is possible to implement a device in which a transmission-only device has only an interleave unit and a reception-only device has only a deinterleave unit.

The present embodiment is characterized in that the circuit configuration of the interleave unit and the deinterleave unit is the same. For example, a deinterleave operation can be performed by changing the increment of the number of shifts input to the interleave unit from i to j. By utilizing this feature, the circuit size can be reduced when applied to half-duplex communication. That is, one transceiver has only an interleave device, the other transceiver has only a deinterleave device, and when performing reverse communication, the interleave device performs a deinterleave operation, and the deinterleave device performs By performing interleaving operation, compared to full-duplex communication,
The circuit scale is halved.

(Embodiment 2) Next, an embodiment in which an error correction code is used together will be described.

In this embodiment, as in the first embodiment, i =
2, j = 3. Therefore, the frame configuration is as shown in FIG. However, the word in the present embodiment is a codeword of an error correction code.

In FIG. 9, reference numeral 91 denotes an error correction encoder;
2 is an interleave device, 93 is a deinterleave device, and 94 is an error correction decoder. Reference numeral 91 denotes error correction encoding of the data, and outputs the data to 92. Reference numeral 92 performs interleaving by arranging input error correction code words in the horizontal direction and outputting the words in the vertical direction. Then, the 93 interleaves the input interleaved data sequence in the vertical direction and outputs the interleaved data sequence in the horizontal direction, thereby performing de-interleaving and outputting the word of the error correction code to 94. 94
Performs error correction decoding on burst errors evenly distributed in each word.

The state of interleaving will be compared with the conventional example of FIG. In the conventional example, as shown in FIG. 6, the data rearrangement rules are different between the odd-numbered frame and the even-numbered frame. In the odd-numbered frame, m × t = 4 burst error correction capability is obtained. The frame has the burst error correction capability of 1. On the other hand, in the present embodiment, the data rearrangement rule is always constant, and the interleaving shown in FIG. 6A is executed for all frames. Therefore, the burst error correction capability is always m × t = 4.

[0042]

The interleave / deinterleave device of the present invention achieves high memory utilization efficiency by writing one symbol data to a free address generated by reading one symbol data from the memory.

Since the same interleave is always performed for every frame, it is not necessary to add interleave information to the frame.

Error correction code m with burst error correction capability t
When words are interleaved, it always has m × t burst error correction capability.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration of an interleave / deinterleave device according to a first embodiment of the present invention.

FIG. 2 is a matrix diagram showing access directions to an m × n matrix memory;

FIG. 3 is a matrix diagram showing a state in which an error correction code having a code length of n is interleaved.

FIG. 4 is a block diagram showing a configuration of a conventional interleave device using two frame memories;

FIG. 5 is a block diagram showing a configuration of a conventional interleave device using only one frame memory;

FIG. 6 is a matrix diagram showing a state in which an error correction code having a code length n = 8 is interleaved using a conventional device.

FIG. 7 is a configuration diagram of a frame according to the first embodiment.

FIG. 8 is a timing chart showing the operation of the first embodiment.

FIG. 9 is a block diagram showing a configuration of an interleave / deinterleave device and an error correction device according to a second embodiment.

[Explanation of symbols]

 Reference Signs List 11 binary counter 12 shift number calculation means 13 cyclic shift means 14 memory a count value b shift number c address signal i shift number increment tx data itx interleave data 15 binary counter 16 shift number calculation means 17 cyclic shift means 18 memory d count value e shift number f address signal j shift number increment irx interleave data rx deinterleave data

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Tomonori Kishimoto 1006 Kadoma Kadoma, Osaka Prefecture Inside Matsushita Electric Industrial Co., Ltd.

Claims (5)

[Claims] 1. i and j are positive integers and k is k = i
+ J, b and e are integers from 0 to k−1, and one frame is composed of 2 ^ i words, and one word is 2 ^ j
An interleaving apparatus for rearranging symbols in a frame with respect to a data sequence composed of symbols, wherein the symbols in the frame are counted from 0 to 2 ＾ k−1, and the count value is represented by a k-bit signal a = (a [K-
1], a [k-2],..., A [1], a [0]), and the initial value of the shift number b is any integer from 0 to k−1, A shift number calculating means for outputting a remainder obtained by dividing b + i by k at the beginning of the frame as a new value of b and outputting the value of b to the end of the frame; and cyclically shifting the output signal a of the binary counter by the shift number b Address signal c = (a [b−
1], a [b-2],..., A [1], a [0], a
[K-1], a [k-2], ..., a [b + 1], a
A cyclic shift means for outputting [b]), and having a k-bit address, wherein the address signal c supplied from the cyclic shift means indicates the same address within a period of time indicating the same address. An interleave device comprising: a memory for reading data and then writing data. 2. i and j are positive integers and k is k = i
+ J, b and e are integers from 0 to k−1, and one frame is composed of 2 ^ i words, and one word is 2 ^ j
A deinterleave device for rearranging symbols in a frame with respect to a data sequence composed of symbols, wherein the symbols in the frame are counted from 0 to 2 ＾ k−1, and the count value is represented by a k-bit signal d = ( d [k-
1], d [k-2],..., D [1], d [0]), and the initial value of the shift number e is any integer from 0 to k-1. A shift number calculating means for outputting a remainder obtained by dividing e + j by k at the beginning of the frame as a new value of e, and outputting the value of e to the end of the frame; and cyclically shifting the output signal d of the binary counter by the shift number e Address signal f = (d [e−
1], d [e-2],..., D [1], d [0], d
[K-1], d [k-2], ..., d [e + 1], d
A cyclic shift means for outputting [e]), and having a k-bit address, wherein the address signal f supplied from the cyclic shift means represents the same address while the same address is being displayed. And a memory for reading data and then writing data. 3. i and j are positive integers, and k is k = i
+ J, b and e are integers from 0 to k−1, and one frame is composed of 2 ^ i words, and one word is 2 ^ j
An interleaving / deinterleaving device for rearranging symbols in a frame with respect to a data sequence composed of symbols, wherein an interleaving section counts the symbols in the frame from 0 to 2 ^ k-1 and counts the count value by k Bit signal a = (a [k−
1], a [k-2],..., A [1], a [0]), and an initial value of the shift number b is set to an arbitrary value from 0 to k−1. First shift number calculating means for outputting an integer, a remainder obtained by dividing b + i by k at the beginning of the frame as k, and outputting the value of b to the end of the frame; and an output signal of the first binary counter address signal c = (a) created by cyclically shifting a by the above-mentioned shift number b.
[B-1], a [b-2], ..., a [1], a
[0], a [k-1], a [k-2], ..., a [b
+1], a [b]), and a k-bit address, and the address signal c supplied from the first cyclic shift means indicates one address. Within the time, data is first read from the same address, and then data is written to the first address.
The deinterleave unit counts the symbols in the frame from 0 to 2 ＾ k−1, and counts the count value as a k-bit signal d = (d [k−
1], d [k-2],..., D [1], d [0]), and an initial value of the shift number e of 0 to k-1 A second shift number calculating means for outputting a remainder obtained by dividing e + j by k at the beginning of the frame as a new value of e and outputting the value of e to the end of the frame; and an output signal of the second binary counter An address signal f = (d) created by cyclically shifting d by the shift number e
[E-1], d [e-2],..., D [1], d
[0], d [k-1], d [k-2], ..., d [e
+1], d [e]), and a k-bit address, and the address signal f supplied from the second cyclic shift means indicates one address. An interleave / deinterleave device comprising: a memory for reading data from the same address and then writing data to the same address in time. 4. The interleave / de-interleave device according to claim 3, wherein the first shift number calculating means and the second shift number calculating means are shared by one shift number calculating means, and the shift number is calculated during the interleaving operation. An interleave / deinterleave device characterized in that the increment of the number of shifts in the calculating means is set to i and the increment of the number of shifts in the shift number calculating means is set to j at the time of the deinterleave operation. 5. The interleave / deinterleave apparatus according to claim 3, wherein one word is one word of a block error correction code.