FIELD OF THE INVENTION

The invention relates to the field of data processing and can be used to aid communication systems which require noise tolerance.

BACKGROUND OF THE INVENTION

Communication systems use interleavers to transform data which has been corrupted by correlated noise into data in which the noise appears to be distributed in time with less correlation. The deinterleaver transforms the data back into its original form. The overall interleave/deinterleave operation is such that the received data is identical to the transmitted data in the absence of noise. Several algorithms have been developed which perform the interleave/deinterleave function. These algorithms lend themselves to different implementations, each with their own advantages and disadvantages.

Two well known algorithms for interleaving and deinterleaving data were developed by John Ramsey and David Forney. John Ramsey's original work contains four different interleavers called type I, type II, type III, and type IV. Figure 1 illustrates Ramsey's original implementation of his type II interleaver. There are two parameters for the interleave, n2 and nl. The n2 parameter specifies how many contiguous symbols in the interleaved sequence over which the minimum spacing nl is valid. The nl parameter specifies the minimum spacing in the original stream that can be contained in any n2 contiguous symbols in the interleaved stream. In Fig. 1 the blocks 101, 102, 103, and 104 are shift registers with delay n2-l. The blocks 106, 107, 108, and 109 are adders which serve as muxes when nl and n2 are constrained appropriately. The constraints on n2 and nl are that n2 and nl+1 must be relatively prime and n2 > nl+1. The commutator switch 105 sequences counter-clockwise for every symbol received at

the input 111. The continuation symbol 110 indicates that the number of shift and add stages is not explicitly specified by the drawing. For this implementation, a total of nl*(n2-l) delay elements are required. The output is from 112.

Figure 2 illustrates a basic Forney type interleaver. The shift registers 200, 201, 202, and 203 are of length specified inside the register and shift the data one position to the right every I ^th input data symbol. For example, the shift register 200 has a total delay of T*I and the shift register 201 has a total delay of 2*T*I. There are a total of I sets of shift registers. The commutators 204 and 205 move one position every input symbol and are synchronized with each other. In this document the value T*I is defined as N. There are a total of I*(I-l)*T/2 delay elements for the interleaver. A forney interleaver is equivalent to ta Ramsey type III (not shown here) when N = nl+1 and I = n2 and T is an integer.

In the state of the art, there are two basic approaches to implementing the algorithms invented by Forney and Ramsey. One approach is with the use of shift registers and this was the technique presented in the inventor's original works.

This technique has the advantage of requiring the smallest number of memory elements. Another approach is with the use of a random access memory (RAM). This technique has the advantage of using a cheaper technology. A diagram contrasting these approaches is shown in Figure 3. In Fig. 3a, the data arrives as 306 and exits either interleaved or deinterleaved as 307. The shift register is 304 and the commutators 308 and 309. The control is shown as 305. In Fig. 3b, the RAM is 300. Data is written into the RAM in 302 and is read from the RAM is 303. The 301 is the address generation and control for the operation.

An apparatus implementing a single deinterleaving algorithm (such as those designed to deinterleave streams interleaved according to the techniques described above) suffers from the drawback of only being able to deinterleave data streams interleaved by a single protocol. This proves particularly troublesome when users wish to design a system that can receive and deinterleave data interleaved using different interleaving algorithms. In the United States, the standard interleaving protocol for Direct Broadcast Satellite (DBS) systems is based on Ramsey's type II algorithm. In Europe, the protocol for DBS systems is based on Forney's algorithm. The result is that users must use a different deinterleaving apparatus

than when they deinterleave DBS data streams initiated in the United States as opposed to data streams from Europe. Similarly, manufacturers of deinterleaving equipment must build different devices for sale in the United States and Europe. What is needed is an apparatus that can be reconfigured to deinterleave streams interleaved according to a plurality of interleaving schemes.

SUMMARY OF THE INVENTION

The present invention provides a cost effective deinterleaving apparatus that is selectively configurable for data streams interleaved according to one of a plurality of data streams (note that since a deinterleaver is also an interleaver this invention also is a configurable interleaving apparatus). This is accomplished with the invention of a single, cost efficient address generation unit that can be used for multiple algorithms by dynamically controlling key parameters during operation. The system level diagram of the deinterleaver is similar to that shown in Fig. 3b and Fig. 4. The key distinction is that the address generation and control unit is capable of deinterleaving a plurality of interleaved data streams with a cost efficient technique. It should be noted that there are no special constraints placed on the RAM by this invention. It can be any standard type, such as dynamic or static, single port or multiple port.

According to the preferred embodiment of the present invention a Generate Write Address block remains the same for all interleaving protocols. It generates an address for writes which restarts every time the last address is written. A Generate Read Address block also remains the same for all interleaving protocols. It generates the read address for a RAM. The parameters specific to each interleaving algorithm are generated in a Parameter Set block. There can be an arbitrary number of Parameter Set blocks, one for each interleaving protocol. A switch selects the correct set of parameters for each interleaving protocol. Such a device allows the deinterleaving apparatus to receive a data stream which has been interleaved according to one of a plurality of interleaving schemes and output the original data stream. A control block is the same for all interleaved data streams and allows the address generation and parameter units to update based on data either being written to or read from the RAM. The Generate Write Address,

Generate Read Address and control blocks are used for all interleaving protocols, thereby providing cost efficiency. Additionally, in the preferred embodiment, the most complexity in these three blocks. This allows the Parameter Set blocks to be produced at very low cost.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 illustrates a Ramsey type II interleaver as described by John L. Ramsey.

Figure 2 illustrates a Forney interleaver similar to description of David G. Forney. Figure 3 illustrates two different implementations of interleaver/deinterleavers in the state of the art.

Figure 4 illustrates a block diagram of one embodiment of a circuit which performs deinterleaving according to a plurality of protocols.

Figure 5 illustrates the a block diagram of the preferred embodiment of the present invention.

Figure 6 illustrates one example of a hardware implementation of the address generation unit for deinterleaving a Ramsey type II or Forney interleaved data stream.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT The present invention is for a deinterleaving apparatus that would be reconfigurable by a user to deinterleave a data stream according to the Ramsey type II or the Forney protocols, or even using a proprietary scheme. This will provide users with a deinterleaver that has greater applicability. More specifically, it allows a user in the United States to receive and deinterleave interleaved data from Europe without having to purchase a deinterleaving apparatus utilizing a different algorithm.

One technique for providing a multipurpose deinterleaver is to include the appropriate circuitry for all desired deinterleavers in a single apparatus and then use a hardware or software switch to engage the desired deinterleaver. Such a system for deinterleaving one of two types of interleaved data is shown in Figure 4 for the

RAM based deinterleave implementation approach. In Fig. 4, the RAM is 400, the data is in 403, and the data out is 404. The two different address generation units and control are shown as 401 and 402. The switch 405 is used to activate the desired deinterleaving algorithm. This "brute-force" scheme has the disadvantage of requiring a completely separate apparatus for each allowable type of interleaved data. For software implementation, requiring multiple separate apparatuses requires multiple sizes of the program memory. For hardware implementation on an integrated circuit, the multiple separate apparatuses require more transistors and therefore more silicon area. In the design of integrated circuits, silicon area is a critical parameter in manufacturing cost and therefore must be minimized wherever possible. Furthermore, the high cost of having a separate apparatus for each deinterleaving protocol gets worse as more protocols are added to the deinterleaver. Figure 5 shows a block diagram of the preferred embodiment of the present invention which is used in place of 301 in Fig. 3 or in place of 401, 402, and 405 in Fig. 4. The Generate Write Address block 500 remains the same for all interleaving protocols. It generates an address for writes which restarts every time the last address is written. The Generate Read Address block 501 remains the same for all interleaving protocols. It generates the read address for the RAM. The parameters specific to each interleaving algorithm are generated in the Parameter Set blocks 502, 503, and 504. There can be an arbitrary number of these units, one for each interleaving protocol. The commutator 505 switches the correct set of parameters into 500 and 501 for each interleaving protocol. When this device is used in place of 301 in Fig. 3, it allows apparatus 300 to receive a data stream 302 which has been interleaved according to one of a plurality of interleaving schemes and output the original data stream to 303. The control block

506 is the same for all interleaved data streams and allows the address generation and parameter units to update based on data either being written to the RAM through 302 or read from the RAM through 303. Because the blocks 500, 501, and 506 are reused for all interleaving protocols, cost efficiency is achieved. Furthermore, this invention places the most complexity in blocks 500, 501, and 506 and therefore the parameter sets 502, 503, and 504 can be very low cost.

Figure 6 shows one possible hardware implementation of the invention of Figure 5. This example deinterleaves two possible types of interleaved data streams, the Ramsey type II interleaved data stream and the Forney interleaved data stream. This example is designed to work with a single port RAM which requires reads and writes to be disjoint in time, hence the mux 605. For this implementation a read always precedes a write since the same address can generated by both the read address 604 and write address 600 circuitry. Another possible hardware implementation for a dual port RAM allows concurrent reads and writes and would eliminate the need for the mux 605. Blocks 605, 606, 607, 608, 609, 610, and all objects labeled 612 are two input muxes. These devices route either the '0' input or the '1' input to the 'm' output based on the value of the select signal arriving at the side of the object. All blocks labeled 611 are summation devices and the block labeled 613 is a subtraction device. All blocks labeled 614 are data storage devices. All blocks labeled 615 are equality comparators, whose output goes active when the equality test is evaluated true. The block 616 is a greater-than-or-equal-to comparator. The Write Address Generation Unit 600 increments linearly through the RAM address space until it reaches the RAM size, selected by the mux 606, at which time it starts over at the first address. The go_write signal tells the write address to increment every time a byte is received at the RAM and is generated by the control 506 (Figure 5).

The Read Address Generation Unit 604 changes the read address when the go_read signal is asserted indicating that data is to be removed from the RAM. The go-read signal is generated by the control 506 and will not begin to assert until the RAM has been completely written once. After this time, the go_read signal always asserts when a new byte is received at the RAM. In other words, once the RAM has been written once, data is read out of the RAM only when data is written into the RAM. To flush the RAM, a dummy byte can be written under control 506. When the read address exceeds the RAM size, muxed through 606, then the RAM size is subtracted from the read address.

The two sets of parameters 601 and 602 are shown in the example of Figure 6. The Ramsey II parameter set 601 provides dynamic information to the Read

Address Generation Unit 604. The Forney parameter set 602 provides fixed information to the Read Address Generation Unit 604. The set of muxes 603 perform the function of the commutator 505 (Figure 5) and is set before deinterleaving occurs. In the set of muxes for this implementation are the RAM size, from mux 606; an additional count number of 0 or 1, from mux 607 the

Ramsey type II nl parameter, from mux 608; a count parameter, from mux 609; and a mux select signal from mux 610. The select signal to mux group 603 chooses among the two interleave types.

The Ramsey type II deinterleave is performed by noticing from Figure 1 that the original data is ordered by offsets of n2 except every nl+1 it is offset by n2+nl+l. The circuit pair 601 and 604 generate the read addresses to extract the original ordering out of the interleaved data stream.

The Forney deinterleave performs by noticing from Figure 2 that Forney interleaved data has the original data ordered by offsets of N+l. Deinterleaving is accomplished by reading in steps of N+l until N*l is reached at which time the read address N*I-(N+1)*I = I is read which is the I ^th data of the original stream. Then steps of N+l continue. The circuit pair 602 and 604 generate the read addresses to extract the data out of the interleaved data stream.

The present invention has been described in terms of specific embodiments incorporating details to facilitate the understanding of the principles of construction and operation of the invention. Such reference herein to specific embodiments and details thereof is not intended to limit the scope of the claims appended hereto. It will be apparent to those skilled in the art that modifications may be made in the embodiment chosen for illustration without departing from the spirit and scope of the invention. Specifically, it will be apparent to one of ordinary skill in the art that the apparatus disclosed above is only illustrative of the preferred embodiment of the present invention and is in no way a limitation.