Patent Publication Number: US-6714606-B1

Title: Integrated services digital broadcasting deinterleaver architecture

Description:
FIELD OF THE INVENTION 
     The present invention relates to memory buffers generally and, more particularly, to an integrated services digital broadcasting (ISDB) de-interleaver architecture. 
     BACKGROUND OF THE INVENTION 
     The Japanese integrated services digital broadcasting (ISDB) standard uses a 203×8 block interleaver before a convolution encoder and after an RS encoder and randomizer. Data bytes are transmitted in the format of 203 bytes/slot, 48 slots/frame, 8 frames/ super frame. The interleaver operates on the n-th slot of every frame in one super frame, where n=0, 1, 2, . . . , 47. Upon receipt, the data bytes must be de-interleaved. 
     Referring to FIG. 1, a block diagram of a conventional block de-interleaver  10  is shown. The block de-interleaver  10  is used to de-interleave super frames in the Japanese integrated services digital broadcasting (ISDB) standard. The block de-interleaver  10  requires two super frame memories  12  and  14  to de-interleave a received signal. The block de-interleaver  10  writes data from the received signal into one super frame memory  12  while presenting data of a previously received signal from the other super frame memory  14 . When one super frame of data is finished, the reading and writing exchange memory frames. 
     In the example of the Japanese ISDB standard, the super frame memory size is 76.125K bytes. The need for two super frame memories doubles the memory used to implement the device. Doubling the memory on a chip increases the cost and decreases the chip yield. A solution is needed that will use less memory to de-interleaved a super frame. 
     SUMMARY OF THE INVENTION 
     The present invention concerns an apparatus comprising a memory, a write pointer, a read pointer and a control circuit. The memory may have a plurality of memory locations accessed by a plurality of addresses. The write pointer may be configured to write data to the memory in response to a sequence of write addresses generated in response to a first control signal. The read pointer may be configured to read data from the memory in response to a sequence of read addresses generated in response to a second control signal. The control circuit may be configured to generate (i) the first control signal, and (ii) the second control signal. The order data is read from said memory may comprise a de-interleaved pattern with respect to the order the data is written to the memory. 
     The objects, features and advantages of the present invention include providing an integrated services digital broadcasting de-interleaver architecture with slightly more than one super frame of memory that may de-interleave a Japanese ISDB standard super frame at a lower cost and/or higher chip yield. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other objects, features and advantages of the present invention will be apparent from the following detailed description and the appended claims and drawings in which: 
     FIG. 1 is a block diagram illustrating a conventional block de-interleaver; 
     FIG. 2 is a block diagram of a circuit  100  illustrating a preferred embodiment of the present invention; 
     FIG. 3 is a diagram illustrating a first round write and read cycle of FIG. 2; 
     FIG. 4 is a diagram illustrating a delay between a read pointer and a write pointer of FIG. 2; 
     FIG. 5 is a diagram illustrating a write operation of a second super frame of data to the super frame memory of FIG. 2; 
     FIG. 6 is a diagram illustrating data stored after rounds  1 - 5 ; 
     FIG. 7 is a diagram illustrating a second round read and write operation; 
     FIG. 8 is a diagram illustrating data of the second super frame received grouped according to output frame; 
     FIG. 9 is a diagram illustrating an additional memory space for simplify ng the second write cycle; and 
     FIG. 10 is a diagram illustrating the grouping of output data according to output frame in the enlarged memory of FIG.  7 . 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring to FIG. 2, a block diagram of a circuit  100  is shown in accordance with a preferred embodiment of the present invention. The circuit  100  may be implemented, in one example, as a Japanese integrated services digital broadcast (ISDB) standard block de-interleaver. The circuit  100  may be configured, in one example, to (i) receive an interleaved data signal (e.g., DATA_IN) at an input  102  and (ii) present a de-interleaved data signal (e.g., DATA_OUT) at an output  104 . The signal DATA_IN and the signal DATA_OUT may be, in one example, Japanese ISDB standard super frames. 
     The circuit  100  may comprise a control circuit  106 , a write pointer  108 , a read pointer  110 , and a memory  112 . The control circuit  106  may have an output  114 , an output  116 , an output  118 , and an input  120 . The control circuit  106  may be configured to generate (i) a first control signal at the output  114  that may be presented to an input  122  of the write pointer  108 , (ii) a data signal at the output  116  that may be presented to an input  124  of the memory  112 , and (iii) a second control signal at the output  118  that may be presented to an input  126  of the read pointer  110 . The input  120  may be configured to receive a data signal from an output  128  of the memory  112  that may be presented to the output  104 . 
     The signal DATA_IN is generally presented to the control circuit  106 . The control circuit  106  generally writes data bytes of the signal DATA_IN to address locations of the memory  112 . The address locations are generally determined by the write pointer  108 . The write pointer  108  may present a sequence of write addresses to the memory  112 . 
     The read pointer  110  may present a sequence of read addresses to the memory  112  in response to the control signal received at the input  126 . 
     The memory  112  may present data from the addresses to an input  120  of the control circuit  106 . In one example, the control circuit  106  may be configured to generate the signal DATA_OUT in response to the data received from the memory  112 . In another example (not shown), the memory  112  may present the signal DATA_OUT directly to the output  104 . 
     When the control circuit  106  is writing the data of a first super frame, the read pointer  110  will generally not start reading data until the write pointer  108  has written a predetermined number of bytes. The initial delay of the read pointer may be defined as an operation window for the circuit  100  (to be described in more detail in connection with FIG.  4 ). To perform the desired de-interleaving function, the data stored in the memory  112  is generally read in a different order than the data was written. 
     The control circuit  102  generally calculates the addresses for reading and writing data according to predetermined mathematical formulas. The mathematical formulas are generally determined so that the order in which the data is written to the memory  112  combines with the order in which the stored data is read from the memory  112  to de-interleave the data. 
     The memory  112  may be, in one example, slightly larger than one conventional super frame memory. The memory  112  may be divided into a number of sections that generally correspond to the number of slots per frame of the signal DATA_IN. Each of the sections may be treated as an I×N array, where I is generally the number of frames and N is generally the number of bytes per slot in the signal DATA_IN. In one example, where DATA_IN is a Japanese integrated services digital broadcast standard super frame, the memory  112  may be divided into  48  sections, where each section is treated as an 8×203 byte array. The memory  112  may be implemented in one example as a Random Access Memory (RAM), a Static RAM (SRAM), a flash memory, or any other memory needed to meet the design criteria of a particular implementation. 
     The following example may illustrate the operation of the memory  112  for the i-th data byte received by the circuit  100 : 
      frame= i /( N×L )= i /(203×48)= i /9744 
     
       
         slot= i %( N×L )/ N=i %(203×48)/203 =i %9744/203 
       
     
     
       
         index= i %( N×L )% N=i %(203×48)%(203)= i %(9744)%(203)= i %(203) 
       
     
     
       
         pos=(frame× N )+index=(frame×203)+index= i /9744×203+ i %(203) 
       
     
     The symbol “%” is used to indicate the remainder of a division (e.g., the modulus function) and the symbol “/” is used to indicate integer division. 
     The value “pos” is the position of i-th byte in the n-th section of the memory  112 , i=0, 1, 2, . . . , 77951, and n=0, 1, 2, . . . , 47. In the example of the Japanese ISDB standard, “frame” may have a value from 0 to 7, “slot” may have a value from 0 to 47, “index” may have a value from 0 to 202, and “pos” may have a value from 0 to 1623. 
     The data bytes are generally received by the circuit  100  at a constant rate. In order to use only one super frame of memory, the reading of data may start before the write pointer  108  has reached the end of one super frame. 
     The following example may illustrate writing data into the memory  112 : 
     For i-th data byte received by the circuit  100 : 
      frame= i /( N×L )= i /(203×48)= i /9744 
     
       
         slot= i %( N×L )/ N=i %(203×48)/203= i %9744/203 
       
     
     
       
         index= i %( N×L )% N=i %(203×48)%203= i %9744%203= i %203 
       
     
     
       
         pos=frame× N +index=frame×203+index=( i /9744)×203+ i %203 
       
     
      where “pos” is the position of the i-th byte in the n-th 203×8 section of the memory  112 . i=0, 1, 2, . . . , 77951 and n=0, 1, 2, . . . , 47. So frame=0, 1, . . . , 7. slot=0, 1, 2, . . . , 47. index=0, 1, 2, . . . , 202. pos=0, 1, 2, . . . , 1623. Also n=slot. 
     For the i-th data byte read from the memory  112  for presentation by the circuit  100 , “in” may be the receiving order and “out” may be the presentation order: 
     
       
         in= i   
       
     
     
       
         out=pos% I× ( N×L )+pos/ I +slot× N =pos%8×9744+pos/8+slot×203 
       
     
     (Note: pos%8×9744=(remainder of pos/8) multiplied by 9744. 
     The amount of delay between receiving a particular byte of data and presenting the particular byte of data may be defined as: 
     
       
         delay=out-in=pos% I ×( N×L ) +pos/ I +slot× N−i =(frame× N +index)% I ×( N×L )+(frame× N +index)/ I +slot× N−i   
       
     
     For example, when i=0: 
     frame=0 
     slot=0 
     index=0 
     
       
         delay=out−in=(frame× N +index)% I ×( N×L )+(frame× N +index)/ I +slot× N−i =(0×203+0)%8×(203×48)+(0×203+0)/8+0× N −0=0 
       
     
     Also for example when i=77951 
     frame=7 
     slot=47 
     index=202 
     
       
         delay=out−in=(frame× N +index)% I ×( N×L )+(frame× N +index)/ I +slot× N−i =(7×203+202)%8×(203×48)+(7×203+202)/8+47×203−77951=7×203×48+202+47×203−77951=0. 
       
     
     For the data between 0 (e.g., a first byte) and 77951 (e.g., a last byte), the delay may either be positive or negative. A positive delay may exist when, at the time for the i-th data byte to be output to the next stage, the data byte is already in the memory  112 . A negative delay may exist when, at the time for the i-th data byte to be output to the next stage, the data byte is not in the memory  112 . A negative delay may indicate that the circuit  100  will generally have to wait until a data byte is received. Since an ISDB system is generally designed to run at a constant data rate, all of the data bytes should generally be sent to the next stage at a constant rate. Therefore, the circuit  100  generally cannot pause, since holes are not allowed. To avoid a negative delay, the read pointer  110  should be delayed to make sure that a particular data byte is in the memory  112  before the time to send the particular data byte to the next stage. 
     If δ is the delay between the read pointer and the write pointer, then the delay between receipt and presentation of a particular data byte may be: 
     
       
         delay=out−in+δ. 
       
     
     The δ should generally be set to a value that will make the delay positive. The minimum limitation may be expressed as the minimum δ required to make sure the delay is greater than 0: 
     
       
         δ≧ N×L×I−N×L −7=77952−9744−7=68201. 
       
     
     If the circuit  100  is designed to use only one super frame memory for continuous operation, the memory  112  generally will not hold more than one super frame of data bytes. Therefore, the maximum limitation may be expressed, in one example, as: 
     
       
         δ≦ N×L×I =77952 
       
     
     For any one super frame memory architecture de-interleaver used in an ISDB decoder, the constraint may be expressed as: 
     
       
           N×L×I−N×L −7≦δ≦ N×L×I   
       
     
     The above constraint may called the operation window for a one super frame memory de-interleaver. The operation window may be used, in one example, as a dynamic FIFO to interface the circuit  100  with a TCM decoder and an RS decoder. 
     In one example, N=11 may be selected to explain the operation of the circuit  100 . The reason for selecting N=11 is that 11%8=3 (e.g., the remainder when 11 is divided by 8 is 3) provides the same result as 203%8=3. The circuit  100  may comprise, in one example, 48 small block de-interleavers (e.g., one for each slot of a Japanese ISDB standard super frame). The operation may be the same for all 48 only one slot will be described in detail. Any operation performed by one de-interleaver memory will be repeated for each slot (e.g., the operations will be repeated in each of the 48 memory segments) before a next operation is started. The operations include reading or writing one slot of data (e.g., 11 bytes in the example, or 203 bytes in ISDB). 
     Referring to FIGS. 3-5, examples of memory dumps illustrating the contents of one of the segments of the memory  112  at various times are shown. The data before being interleaved may be a simple ramp from 0 to 87. For one block (e.g., 11×8=88 bytes), the data bytes received by the block would generally be 0, 11, 22, 33, 44, 55, 66, 77, 1, 12, . . . . The format of the memory dump is generally “information(address)”. During the first round write operation (e.g., FIG.  3 ), the write pointer  108  generally increments from memory address 0 to 87. The read pointer  110  generally follows the pattern 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 1, 9, 17, . . . . The address accessed by the write pointer  108  (e.g., WADDR) may be expressed, in one example, as “WADDR=WINDEX” (e.g., the write index). The address accessed by the read pointer  110  (e.g., RADDR) may be expressed, in one example, as “RADDR RFRAME+RINDEX×8.” 
     The values WINDEX and RINDEX may serve as the respective indices for the write pointer  108  and the read pointer  110 . The values WINDEX and RINDEX may be different for the same incoming byte number. The values WINDEX and RINDEX are generally the sequence numbers for writing and reading operations, respectively. The value RFRAME may be the number of the output frame of the data. For example, the information byte “11” is generally received second for the write operation (e.g., WINDEX=1) and is generally read 12 th  (e.g., RINDEX=11). When WADDR and RADDR are the same, the write operation and the read operation are generally performed on the same memory location. 
     According to the operation window discussed above, the read operation in a given segment of the memory  112  will generally not start until the write operation in the same segment has started the last slot of data. Otherwise, the read pointer  110  may overtake the write pointer  108 . After the write pointer  108  has gone through all the shaded area, the read pointer  110  will start the beginning (e.g., FIG.  4 ). When the write pointer  108  has finished writing address  87  (e.g., 1691 for ISDB), the read pointer  110  will generally have finished reading out the data bytes of the first slot. The write pointer  108  and the read pointer  110  will generally not stop or wait for each other. The read pointer  110  will generally continue down the second column. The write pointer  108  will generally change direction and begin moving down the columns starting with the first column. The write pointer  108  will generally only use the space not occupied by unread data bytes (e.g., FIG.  5 ). The first column is generally the only slot of 11 bytes that is empty (e.g., the data has already been read). The next 11 bytes of data received by the circuit  100  will generally be written into the 11 bytes of the first column. 
     Referring to FIG. 6, memory dumps of a representative segment of the memory  112  illustrating the location of written information after rounds  1 - 5  are shown. The read and write address calculations of a current round are generally different from a previous round. As the read and write operations are performed, the address calculations will generally become more and more complicated. The read and write address calculations should generally be done separately due to the delay between the read pointer  110  and the write pointer  108  and the different values of frame, slot and index. 
     The write pointer  108  generally follows the read pointer  110  at the same slot or one slot later. The sequence of addresses to be used by the write pointer  108  may be, in one example, copied from the previous address mapping of the read pointer  110 . If the write address mapping is considered over an 8×11 RAM, then the read address mapping will generally be considered over an 11×8 RAM. Comparing the round  0  address mapping to the round  1  address mapping generally illustrates that the RAM is treated as having been converted from 11×8 to 8×11. A similar result may be found by comparing the round  2  mapping to the round  1  mapping. The read address calculations may convert the 11×8 read address mapping to 8×11 and may then use the 11×8 for the next round of reading. 
     If “i” is the sequence number of a byte in a super frame, N is 11 or 203 for ISDB, L is 48, and I is 8, then, for one example: 
     
       
         frame= i /( N×L ) 
       
     
     
       
         slot= i %( N×L )/ N   
       
     
      index= i %( N×L )% N   
     
       
         pos=frame+(index× I ) 
       
     
     
       
         raddr[pos]=raddr[pos]% N×I +raddr[pos]/ N   
       
     
     The value “pos” is generally the sequence number of the byte i in one of the segments of the memory  112 . The above reading address formula incorporates the I×N conversion. 
     Such a method will generally use one extra N×I piece of memory to remember the reading addresses. After each reading the address is generally updated to the address for the next round of reading. Since the writing address is copied from the previous reading address, one extra N memory is generally needed. 
     The total memory generally needed for chip implementation of the embodiment described above may be: 
     
       
           N×I×L× 8+( N×I+N )×log 2 ( N×I ) 
       
     
     For an ISDB application where N=203, I=8, L=48, and the address memory is 11 bits, the total memory needed may be: 
     
       
         203×8×48×8+(203×8+203)×log 2 (203×8)=643, 713(bits) 
       
     
     In general, the read address iteration will eventually repeat to the initial state. For an 11×8 block de-interleaver, the read address will generally return to the first round patterns after 28 iterations. For a 203×8 ISDB block de-interleaver, the iteration number is generally  180 . 
     For a chip implementation, the read address mapping calculation should generally start with a valid read address mapping, to avoid generating the wrong results and not returning to the first state. Since there is generally a delay between the read pointer  110  and write pointer  108 , the read address for the memory should generally be initialized so as to take into account the different start positions. 
     Referring to FIG. 7, a diagram illustrating an alternative method of writing and reading data to the memory  112  is shown. The alternative method generally comprises a first and a second round. In the first round, data is generally written by rows and read by columns. During the second round, the writing and reading directions are exchanged and writing and reading are generally not to and from sequential addresses, respectively. 
     During the second round of writing, the write pointer  108  may be configured to increment the write address to M, where M%I=0 (e.g., 16 for the current example or 208 for ISDB), for each data byte written. When the write pointer  108  reaches the end of a column or would jump out of range, the write pointer  108  generally returns to a first available space in the same column. The write pointer  108  generally continues in this manner until the column is filled. After a column is full, the write pointer  108  generally moves to the next column and repeats the steps. 
     Referring to FIG. 8, a diagram illustrating the contents of a segment of the memory  112  after a second round write operation is shown. The data bytes are shown grouped by output frames. The non-continuous pattern may make calculating read addresses complex. 
     Referring to FIG. 9, a diagram illustrates the addition of memory to each segment of the memory  112 . In general, enough memory is added to each slot segment so that the memory for storing a slot is evenly divisible by the number of frames (e.g., a 203×8 segment would be expanded to 208×8). 
     Referring to FIG. 10, a diagram illustrating the result of the added memory on the organization of data bytes is shown. The data bytes of each output frame are generally stored in contiguous locations and read address calculations are generally simplified. 
     In the first round of writing and reading, the addressing of the memory  112  is generally similar to the addressing described in connection with round one of FIG.  3 . The additional memory space is generally left unused. In the second round of writing, the additional memory is generally used to facilitate grouping the data bytes by frame (e.g., as shown in FIG.  7 ). 
     During the second round of reading, the read pointer  110  may be configured to address M/I values from each column. The read pointer is generally moved back to the first column and the control circuit  106  generally reads the next M/I rows of data. The control circuit  106  repeats the process until all of the data has been read. The control circuit  106  will generally cycle through the first and second rounds as long as data is received. 
     If “i” is the sequence number for a particular data byte in one super frame of data bytes, N is 11 or 203 for ISDB, L is 48, I is 8, and M is the number of bytes in an expanded column (e.g., 16 in the present example, or 208 for ISDB), the sequence of addresses generated by the control circuit  106  may be calculated according to the following criteria: 
     
       
           M =( N+I− 1)/ I×I.   
       
     
     The sequence of addresses used to control writing to the memory  112  during the first and second rounds may be described by the following criteria: 
     
       
         frame= i /( N×L ) 
       
     
     
       
         slot= i %( N×L )/ N   
       
     
     
       
         index= i %( N×L )% N   
       
     
     
       
         write_pos=(frame× N )+index 
       
     
     for the first round of writing, 
     
       
         write_address( i )=write_pos/ I +write_pos% I×M;   
       
     
     for the second round of writing, 
     
       
         write_address( i )=write_pos% M/I +write_pos% I×M/I +write_pos/ M×M.   
       
     
     The sequence of addresses used to control reading from the memory  112  during the first and second rounds may be described by the following criteria: 
     
       
         frame= i /( N×L ) 
       
     
     
       
         slot= i %( N×L )/ N   
       
     
     
       
         index= i %( N×L )% N   
       
     
     
       
         read_pos=(frame× M )+index 
       
     
     for the first round of reading, 
      read_address( i )=read_pos 
     for the second round of reading, 
     
       
         read_address( i )=index%( M/I )+index/( M/I )× M +frame×( M/I ). 
       
     
     The total memory generally needed for de-interleaving a super frame of data in accord with the method described above may be determined by the following equation: 
     
       
         Memory Size(bits)= M×I×L× 8. 
       
     
     For an ISDB application, N=203, I=8, L=48, and M according to the present invention will generally be 208. The total memory needed will generally be: 
     
       
         (208×8×48×8)=638, 976 bits, or 78K bytes. 
       
     
     The amount of memory needed may be reduced further. The last 5 bytes of memory for each slot are generally not used in either the first round or the second round of writing and reading. Using the formula from above, the memory size may be reduced to: 
     
       
         (208×8−5)×48×8=637, 056 bits, or 77.766K bytes. 
       
     
     While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the spirit and scope of the invention.