Decoding apparatus with de-interleaving efforts distributed to different decoding phases and related decoding method thereof

A decoding apparatus includes a memory device and a decoding circuit. The memory device is arranged for storing a data block with inter-row interleaving in a plurality of data rows of the data block and without intra-row interleaving in each of the data rows. The decoding circuit is coupled to the memory device. The decoding circuit is arranged for accessing the memory device to perform a first decoding operation with inter-row de-interleaving memory access, and accessing the memory device to perform a second decoding operation with intra-row de-interleaving memory access.

BACKGROUND

The disclosed embodiments of the present invention relate to a decoding scheme, and more particularly, to a decoding apparatus with de-interleaving efforts distributed to different decoding phases (e.g., a linear/sequential decoding phase and an interleaved decoding phase) and related decoding method thereof.

Data signals, in particular those transmitted over a typically hostile channel, are susceptible to channel noise/interference. Various methods of error correction coding have been developed in order to minimize the adverse effects that a hostile channel has on the integrity of the transmitted data. This is also referred to as lowering the bit error rate (BER), which is generally defined as the ratio of incorrectly received information bits to the total number of received information bits. Error correction coding generally involves representing digital data in ways designed to be robust with respect to error bits. Hence, error correction coding may enable a communications system to recover original data from a signal that has been corrupted due to the undesired channel noise/interference.

For example, turbo codes may be used in the communications system, such as a Wideband Code Division Multiple Access (W-CDMA) system, for channel coding. Regarding the turbo coding system, the input data of a data block may be rearranged with an interleaver and then encoded with the same method as that applied to the original input data. In this way, the data block is encoded with a particular coding method, resulting in an encoded data having systematic bits and two sets of parity bits included therein. The encoded data is combined in some manner to form a serial bit stream and transmitted from a turbo encoding apparatus at a transmitter end to a turbo decoding apparatus at a receiver end through the channel. In general, a conventional turbo decoding apparatus uses an iterative algorithm between two soft-input soft-output (SISO) decoders, and therefore exchanges information between the SISO decoders in order to improve error correction performance.

To achieve a higher transmitted data rate, a possible solution is to apply parallel processing for turbo code decoding. For example, the turbo decoding apparatus may use SISO decoders, each having multiple decoder cores, for processing codeword segments simultaneously, thus providing a higher throughput without increasing the clock speed. However, the decoding performance of such a turbo decoding apparatus may be heavily affected by the interleaver design. Regarding a third generation (3G) communications system (e.g., W-CDMA system), a rectangular interleaver with inter-row permutation and intra-row permutation is employed by the turbo decoding apparatus. However, the rectangular interleaver is particularly designed for rich randomness without considering the multi-core turbo decoder implementation at that time. In other words, this parallel processing approach raises a memory contention problem caused by multiple accesses of the same memory bank in a memory device. For example, data bits of a data block to be decoded are sequentially stored into a memory device. Specifically, the data block to be decoded is stored in the memory device without inter-row permutation and intra-row permutation applied thereto. Hence, data bits of the data block to be decoded are stored in memory banks of the memory device in an original successive bit sequence. Regarding the conventional turbo decoder design, a first SISO decoder is arranged to refer to first parity bits of the data block to perform a decoding operation without inter-row de-interleaving and intra-row de-interleaving memory accesses due to the fact that the first parity bits are derived from the non-interleaved input data. However, regarding a second SISO decoder of the decoding apparatus, it is required to refer to second parity bits to perform a decoding operation with inter-row de-interleaving and intra-row de-interleaving memory accesses due to the fact that the second parity bits are derived from an interleaved input data. Hence, when the second SISO decoder is implemented using a multi-core decoder, it is possible that multiple decoder cores may request the desired data bits to be decoded from the same memory bank, which results in memory contention. When the memory contention occurs, only one decoder core is allowed to fetch the requested data bits from a target memory bank, and the remaining decoder cores need to wait. As a result, before the requested data bits are available, the decoding operation performed by the remaining decoder cores is stalled.

In view of the foregoing, there is a need for an innovative contention-free memory access for realizing a high-throughput multi-core turbo decoding apparatus.

SUMMARY

In accordance with exemplary embodiments of the present invention, a decoding apparatus with de-interleaving efforts distributed to different decoding phases (e.g., a linear/sequential decoding phase and an interleaved decoding phase) and related decoding method thereof are proposed, to solve the above-mentioned problem.

According to a first aspect of the present invention, an exemplary decoding apparatus is disclosed. The exemplary decoding apparatus includes a memory device and a decoding circuit. The memory device is arranged for storing a data block with inter-row interleaving in a plurality of data rows of the data block and without intra-row interleaving in each of the data rows. The decoding circuit is coupled to the memory device. The decoding circuit is arranged for accessing the memory device to perform a first decoding operation with inter-row de-interleaving memory access, and accessing the memory device to perform a second decoding operation with intra-row de-interleaving memory access.

According to a second aspect of the present invention, an exemplary decoding method is disclosed. The exemplary decoding method includes the following steps: utilizing a memory device to store a data block with inter-row interleaving in a plurality of data rows of the data block and without intra-row interleaving in each of the data rows; performing a first decoding operation with inter-row de-interleaving memory access by accessing the memory device; and performing a second decoding operation with intra-row de-interleaving memory access by accessing the memory device.

DETAILED DESCRIPTION

The concept of the present invention is to employ interleaved memory arrangement and proper memory access scheduling of decoder cores to thereby avoid/mitigate the memory contention problem. Specifically, due to the interleaved memory arrangement, a balanced de-interleaving design for a decoding circuit, having multiple decoder cores and operating in different decoding phases, is provided such that the decoding circuit operating in one decoding phase and the decoding circuit operating in another decoding phase would share the de-interleaving efforts. With the help of the balanced de-interleaving design as proposed in the present invention, the contention-free memory access for multiple decoder cores can be achieved through proper memory access scheduling. Further description is detailed as below.

FIG. 1is a block diagram illustrating a decoding apparatus according to a first embodiment of the present invention. The exemplary decoding apparatus100may be a turbo decoding apparatus used for a 3 G communications system, such as a W-CDMA system. However, this is for illustrative purposes only. In practice, any decoder architecture employing the proposed techniques for achieving a contention-free memory access falls within the scope of the present invention. As shown inFIG. 1, the decoding apparatus100includes a memory device102and a decoding circuit103. In a logic sense, the decoding circuit103may be regarded as having a plurality of decoders (e.g., SISO decoders) including at least a first decoder104and a second decoder106. In a physical sense, the decoding circuit103may employ a hardware sharing technique to make a single decoder with multiple decoder cores operate in a time-division manner. More specifically, when the decoding circuit103operates in a linear/sequential decoding phase, the single decoder with multiple decoder cores (i.e., the first decoder104) is operative; and when the decoding circuit103operates in an interleaved decoding phase, the same single decoder with multiple decoder cores (i.e., the first decoder104) is operative to act as the second decoder106. However, this is for illustrative purposes only, and is not meant to be a limitation of the present invention. That is, implementing the decoding circuit103with two sets of decoder cores may also fall within the scope of the present invention.

The memory device102serves as a systematic information memory. Hence, the memory device102is used to buffer a data block D_IN composed of data bits (e.g., soft decisions/soft bits corresponding to systematic bits), and includes a plurality of memory banks112. Each of the first decoder104(e.g., a single decoder operating in the linear/sequential decoding phase) and the second decoder106(e.g., the single decoder operating in the interleaved decoding phase) is a multi-core decoder used for parallel decoding of multiple codeword segments. Therefore, the first decoder104includes a plurality of decoder cores114, and the second decoder106also includes a plurality of decoder cores116, where each decoder core is responsible for successively decoding multiple codeword segments in multiple cycles when granted to fetch soft bits of these codeword segments in one cycle under the proposed memory access scheduling. Details of the proposed memory access scheduling will be described later. It should be noted that the number of memory banks122, the number of decoder cores114and/or the number of decoder cores116may be adjusted, depending upon actual design requirement/consideration.

As the decoding apparatus100is a turbo decoding apparatus in this embodiment, there are adders121,122used for getting extrinsic information. In addition, interleaver123and de-interleavers124,125are also included in the decoding apparatus100, where an output of the de-interleaver125acts as a decoded data block D_OUT composed of decoded data bits. For the first decoding iteration, the soft decisions (soft bits) corresponding to systematic bits and the soft decisions (soft bits) corresponding to the first parity bits DP1are used by the first decoder104in order to decode a first constituent code. The first decoder104outputs the Log Likelihood Ratios (LLRs) of the transmitted bits, and they are used to help the decoding performed by the second decoder106. However, they cannot be used directly and need to be processed so that they are in a format suitable to be fed into the second decoder106. First, extrinsic values are obtained at the adder121and then interleaved at the interleaver123, in order to replicate the interleaving applied at the transmitter end on the sequence of bits to be encoded. The decoding performed by the second decoder106uses the extrinsic information generated by first decoder104with the soft decisions (soft bits) corresponding to interleaved systematic bits and the soft decisions (soft bits) corresponding to the second parity bits DP2. At the output of the second decoder106, a new sequence of LLRs is generated for the sequence of transmitted bits. The LLRs are used by the adder122to calculate the extrinsic information generated by the second decoder106. After de-interleaving at the de-interleaver124, this extrinsic information can be used, in subsequent decoding iterations, by the first decoder104.

As mentioned above, each of the first decoder104and the second decoder106needs to fetch soft decisions (soft bits) corresponding to systematic bits from the memory device102. Hence, to avoid multiple decoder cores114/116of the same decoder104/106from contending for memory access of the memory device102, data bits (e.g., soft bits) of the data block D_IN are stored in the memory device102with a proposed interleaved arrangement. Specifically, the memory device102is arranged for storing the data block D_IN with inter-row interleaving in a plurality of data rows of the data block D_IN and without intra-row interleaving in each of the data rows.

As shown inFIG. 1, the proposed memory arrangement is applied to the memory device102, which serves as a systematic information memory used to buffer the data block D_IN composed of data bits (e.g., soft decisions/soft bits corresponding to systematic bits). However, the proposed memory arrangement may be applied to an extrinsic information memory. Please refer toFIG. 11, which is a block diagram illustrating a decoding apparatus according to a second embodiment of the present invention. The major difference between the decoding apparatuses1100and100is that the decoding apparatus1100has a memory device1102serving as an extrinsic information memory, where the memory device1102is used to buffer a data block composed of data bits (e.g., extrinsic information generated from the adders121and122). Thus, an output of the interleaver123inFIG. 1is now read from the memory device1102having the proposed interleaved memory arrangement, and an output of the de-interleaver124inFIG. 1is now read from the memory device1102having the proposed interleaved memory arrangement. In this embodiment, regarding the data block D_IN composed of data bits (e.g., soft decisions/soft bits corresponding to systematic bits), it is transmitted to the first decoder102and the second decoder106in a conventional manner, where an interleaver1104is implemented to provide interleaved soft decisions/soft bits to the second decoder106.

In a preferred embodiment, the proposed memory arrangement is applied to the memory device102, which serves as a systematic information memory used to buffer the data block D_IN composed of data bits (e.g., soft decisions/soft bits corresponding to systematic bits), and is also applied to the memory device1102, which serves as an extrinsic information memory used to buffer the data block composed of data bits (e.g., extrinsic information). Please refer toFIG. 12, which is a block diagram illustrating a decoding apparatus according to a third embodiment of the present invention. Compared to the aforementioned decoding apparatuses100and1100, the decoding apparatus1200would have better decoding performance due to contention-free memory access of the systematic soft decisions/soft bits and the extrinsic information.

A person skilled in the art should readily understand technical features of the interleaved memory arrangement of the memory device1102and the associated memory access scheduling of decoder cores to access extrinsic information from the memory device1102after reading the description directed to the interleaved memory arrangement of the memory device102and the associated memory access scheduling of decoder cores to access systematic soft decisions/soft bits from the memory device102. Thus, for clarity and simplicity, the following description is only directed to the interleaved memory arrangement of the memory device102and the associated memory access scheduling of decoder cores to access the memory device102. Further description directed to the interleaved memory arrangement of the memory device1102and the associated memory access scheduling of decoder cores to access the memory device1102is therefore omitted for brevity.

Please refer toFIG. 2, which is a diagram illustrating an example of the interleaved memory arrangement employed by the decoding apparatus100shown inFIG. 1. Suppose that an information block (e.g., a data block D_IN′ shown inFIG. 2) is encoded at an encoding apparatus (e.g., a turbo encoding apparatus) and then transmitted to a decoding apparatus (e.g., a turbo decoding apparatus) for decoding. Regarding one turbo encoding procedure for the data block D_IN′, the data block D_IN′ is processed by one turbo encoder in a row-by-row sequence. As shown inFIG. 2, the data block D_IN′ includes a plurality of data bits χ00-χ40, χ01-χ41, χ02-χ42, χ03-χ23located at successive data rows, respectively. Thus, the data bits χ00-χ40, χ01-χ41, χ02-χ42, χ03-χ23are read in order and then processed by the turbo encoder to generate the aforementioned first parity bits.

Regarding another turbo encoding procedure for the data block D_IN′, the data block D_IN′ is processed by an interleaver (e.g., a rectangular interleaver) to become an interleaved data block D_IN″, and then the interleaved data block D_IN″ is processed by another turbo encoder in a column-by-column sequence. As shown inFIG. 2, inter-row permutation is applied to all data rows in the data block D_IN′, and then intra-row permutation is applied to each data row of the data block D_IN. Specifically, regarding the inter-row permutation, the first data row in the data block D_IN′ becomes the second data row in the data block D_IN, the second data row in the data block D_IN′ becomes the fourth data row in the data block D_IN, the third data row in the data block D_IN′ becomes the first data row in the data block D_IN, and the fourth data row in the data block D_IN′ becomes the third data row in the data block D_IN. Regarding the intra-row permutation, the data bits χ02-χ42in the first row of the data block D_IN are interleaved to become data bits χ32, χ42, χ12, χ22, χ02in the first row of the data block D_IN″, the data bits χ00-χ40in the second row of the data block D_IN are interleaved to become data bits χ00, χ20, χ40, χ10, χ30in the second row of the data block D_IN″, the data bits χ03-χ23and padded dummy bits ‘0’ in the third row of the data block D_IN are interleaved to become bits χ23, 0, χ13, χ03, 0 in the third row of the data block D_IN″, and the data bits χ01-χ41in the fourth row of the data block D_IN are interleaved to become data bits χ41, χ11, χ31, χ01, χ21in the fourth row of the data block D_IN″. Next, data bits χ32-χ41in the first column of the data block D_IN″, data bits χ42-χ11in the second column of the data block D_IN″ (dummy bits omitted), data bits χ12-χ31in the third column of the data block D_IN″, data bits χ22-χ01in the fourth column of the data block D_IN″, and data bits χ02-χ21in the fifth column of the data block D_IN″ (dummy bits omitted) are read in order and then processed by a turbo encoder to generate the aforementioned second parity bits.

The systematic bits of the data block D_IN′ and the associated first and second parity bits are transmitted from a transmitter end of a communications system (e.g., a W-CDMA system) to a receiver end of the communications system. Regarding the turbo decoding procedure performed at the receiver end, soft decisions (soft bits) corresponding to the received data block D_IN′ undergoes inter-row permutation before stored into the memory device102shown inFIG. 1. It should be noted that no intra-row permutation is applied to each data row. For example, the memory device102has four memory banks. Thus, soft bits corresponding to data row [χ02χ12χ22χ32χ42] of the data block D_IN are stored in the first memory bank, soft bits corresponding to data row [χ02χ12χ20χ30χ40] of the data block D_IN are stored in the second memory bank, soft bits corresponding to data row [χ03χ13χ230 0] of the data block D_IN are stored in the third memory bank, and soft bits corresponding to data row [χ01χ11χ21χ31χ41] of the data block D_IN are stored in the fourth memory bank. The first decoder104is used for referring to the first parity bits to decode data bits χ00-χ23in a successive bit sequence. However, as the memory device102stores a data block with permuted data rows, the first decoder104is therefore arranged for accessing the memory device102to perform a first decoding operation with inter-row de-interleaving memory access. More specifically, the first decoder104does not sequentially access the memory banks in a row-by-row sequence due to the fact that the memory device102has an inter-row permuted arrangement of data rows. Thus, when performing the first decoding operation according to the first parity bits, the first decoder104accesses the second memory bank, the fourth memory bank, the first memory bank and the third memory bank, sequentially. In this way, data bits χ00-χ40, χ01-χ41, χ02-χ42and χ03-χ23are sequentially read and then processed by the first decoder104for error detection and correction. To put it simply, the first decoder104shares the inter-row de-interleaving effort due to the interleaved memory arrangement for data bits (e.g., soft bits) to be decoded.

Further, as the memory device102stores a data block with data rows that are inter-row permuted only, the second decoder106is arranged for accessing the memory device102to perform a second decoding operation with intra-row de-interleaving memory access. More specifically, due to the fact that the memory device102does not have an intra-row permuted arrangement for each data row, the second decoder106does not read across different memory banks in a column-by-column sequence for sequentially fetching soft bits located at the same column but different memory banks. Thus, when performing the second decoding operation according to the second parity bits, the second decoder106successively accesses the first memory bank to the fourth memory bank for getting desired soft bits, including the fourth data bit χ41from the first memory bank, the first data bit χ00from the second memory bank, the third data bit χ23from the third memory bank, and the fifth data bit χ41from the fourth memory bank. Next, the second decoder106successively accesses the first memory bank, the second memory bank and the fourth memory bank for getting desired soft bits, including the fifth data bit χ42from the first memory bank, the third data bit χ20from the second memory bank, and the second data bit χ11from the fourth memory bank. The following memory access for remaining data bits may be deduced by analogy and thus omitted here for brevity. In this way, data bits χ32-χ41, χ42-χ11, χ12-χ31, χ22-χ01and χ02-χ21are successively read and then processed by the second decoder106for error detection and correction. To put it simply, the second decoder104shares the intra-row de-interleaving effort due to the interleaved memory arrangement for data bits (e.g., soft bits) to be decoded.

For clarity and simplicity, the rectangular interleaver design with four rows is shown inFIG. 2. However, this is merely an example for illustrating features of the present invention. In practice, the row number R of a rectangular interleaver may depend on the number of input bits K, as shown below.

Thus, based on the setting of the row number R of the rectangular interleaver, the inter-row permutation would have pre-defined patterns as shown in the following table.

Regarding the inter-row permutation patterns, T(i) represents the original row index of the permuted index i. Taking R=5 for example, a data row with an original row index ‘4’ would become a data row with a permuted row index ‘0’, a data row with an original row index ‘3’ would become a data row with a permuted row index ‘1’, a data row with an original row index ‘2’ would become a data row with a permuted row index ‘2’, a data row with an original row index ‘1’ would become a data row with a permuted row index ‘3’, and a data row with an original row index ‘0’ would become a data row with a permuted row index ‘4’. Hence, after the inter-row permutation is applied to data rows of an original data block, an adjusted data block would have data rows arranged in a reverse order. As a person skilled in the art can readily understand details of the rectangular interleaver, further description is omitted here for brevity.

In one exemplary design, the second decoder106is configured to have M decoder cores used for parallel decoding, where each of the M decoder cores is arranged for decoding N data bits per cycle, and M and N are positive integers. The M decoder cores are expected to divide the decoding time by a factor of M, thereby increasing the throughput. Regarding the memory device102, it is configured to have multiple memory banks for storing the data rows. Besides, the inter-row interleaving is properly configured to ensure that at least M*N valid data bits are always obtained through simultaneously accessing the memory banks. In one exemplary turbo decoder design, M=4 and N=2. Thus, the second decoder106is a quad-core decoder, and each decoder core of the quad-core decoder is a radix-4 MAP core/engine implemented to decode a codeword segment composed of 2 soft bits per cycle.

In a case where each decoder core116in the second decoder106is a radix-4 MAP core implemented to decode two soft bits per cycle (i.e., M=4 and N=2), the memory device102is preferably configured to meet the requirement for an 8/10 property. Thus, the memory device102would have 10 memory banks rather than 8 memory banks. As mentioned above, there may be dummy bits added to fit the interleaver size. Hence, when 10 memory banks are employed, the interleaved arrangement of the soft bits can make each of the 4 decoder cores116always get 8 valid soft bits through simultaneously accessing the 10 memory banks. Specifically, for any 10 consecutive interleaved bits (which may include dummy bit(s)) read across the 10 memory banks, the 8/10 property can be fulfilled with the inter-row permutation. To put it simply, the 4 decoder cores116are arranged to access the memory device102in a round-robin manner, where each decoder core116obtains at least 8 valid bits in one memory access cycle. That is, each decoder core116can always read at least 8 soft bits of the systematic information from the 10 memory banks112in the memory device102. As each decoder core116would read all memory banks112on its turn whenever there are less than 8 soft bits to last for the next 4 cycles, the row swapping is accommodated by the current memory access which reads all memory banks. This avoids separating two swapped rows in two memory accesses as well as the extra buffer and delay required to finish the row swapping.

Based on the above-mentioned table showing possible inter-row permutation patterns for different row numbers of the rectangular interleaver, the 10 memory banks would be used to store data rows interleaved due to inter-row permutation. The distribution of the inter-row permuted rows for different row numbers of the rectangular interleaver is illustrated in the following table.

Please refer toFIG. 3in conjunction withFIG. 4for better understanding of technical features of the present invention.FIG. 3is a diagram illustrating a memory access order of four decoder cores in the second decoder106according to an embodiment of the present invention.FIG. 4is a timing diagram of the parallel decoding operation performed by the four decoder cores in the second decoder106according to an embodiment of the present invention. Consider an exemplary case where 8 valid data bits are available in the memory device102for each memory access. It should be noted that this is for illustrative purposes only, and is not meant to be a limitation of the present invention. Therefore, the decoder cores116_1,116_2,116_3and116_4of the second decoder106take turns to obtain 8 data bits (e.g., soft bits) from the memory device102, where 20 data rows of a data block are stored in 10 memory banks in an inter-row permuted fashion. Hence, when one of the decoder cores116_1-116_4is granted to access the memory device102, the required 8 data bits would be located at different memory banks, respectively. In this way, each of the decoder cores116_1-116_4is capable of getting the required 8 data bits in one memory access cycle by simultaneously reading 8 memory banks selected from the 10 memory banks of the memory device102. As can be seen fromFIG. 4, the decoder core116_1simultaneously gets 8 data bits D00-D07at T0, decodes first two data bits D00and D01in one cycle between T0and T1, decodes next two data bits D02and D03in one cycle between T1and T2, decodes next two data bits D04and D05in one cycle between T2and T3, and decodes last two data bits D06and D07in one cycle between T3and T4. After the data bits D00-D07have been completely decoded during 4 cycles, the decoder core116_1simultaneously gets the next 8 data bits D00′-D07′ at T4, decodes first two data bits D00′ and D01′ in one cycle between T4and T5, decodes next two data bits D02′ and D03′ in one cycle between T5and T6, decodes next two data bits D04′ and D05′ in one cycle between T6and T7, and decodes last two data bits D06′ and D07′ in one cycle between T7and T8. Therefore, as the decoder core116_1gets 8 data bits simultaneously and decodes two data bits per cycle, the decoder core116_1only needs to access the memory device102every four cycles. Similarly, as can be seen fromFIG. 4, each of the remaining decoder cores116_2-116_4only needs to access the memory device102every four cycles. However, when one decoder core is accessing the memory device102in a current cycle, the other decoder cores would not access the memory device102since the data bits to be decoded have been fetched in previous cycles. Hence, the decoder cores116_1-116_4of the second decoder106would have contention-free memory access of the memory device102.

Please note that the decoder cores116_1-116_4are granted to access the memory device102at different cycles. Thus, each of the decoder cores116_1-116_4can be selectively used for computing forward metrics α first or backward metrics β first, where the forward metrics and the backward metrics are both computed by each decoder core in the current operation to facilitate the window-based approximation utilized in the later operation for next round of iteration. More specifically, properly having interleaved decoding directions for the current operation can bring better initial forward and backward metrics for the window-based approximation in the later operation. In this way, with a proper decoding direction setting of the decoder cores116_1-116_4, full-trace decoding may be achieved by using the second decoder106.

Regarding the first decoder104, it may include M′ decoder cores used for parallel decoding, where each of the M′ decoder cores is arranged for decoding N′ data bits per cycle. Besides, the M′ decoder cores are categorized into K′ decoder core groups, where each decoder core group contains M′/K′ decoder cores, and M′, N′ and K′ are positive integers. Besides, the K′ decoder core groups are arranged to access the memory device102in a round-robin manner. As the memory device102has multiple memory banks for storing the data rows, the inter-row interleaving is properly configured to ensure that all decoder cores114in each decoder core group do not access the same memory bank simultaneously. In one exemplary turbo decoder design, M′=M=4, N′=N=2, K′=2, and the number of memory banks is equal to 10. Therefore, the first decoder104is a quad-core decoder, and each decoder core of the first decoder104is a radix-4 MAP core/engine implemented to decode two data bits (e.g., soft bits) per cycle. As the first decoder104has two decoder core groups each having two decoder cores, and the two decoder core groups are arranged to access the memory device102in a round-robin manner, each decoder core114of the first decoder104is configured to get 4 valid data bits. In this embodiment, the 4 valid data bits are consecutive data bits that are packed together and read from the memory device102. Thus, each decoder core of the first decoder104is capable of easily reading the desired 4 valid data bits from the memory device102in one memory access cycle. It should be noted that, compared to a pack-8 format, the proposed pack-4 format would have a good trade-off among access complexity, power and area.

When the pack-4 format is employed, only two decoder cores of the same decoder core group would access memory banks of the memory device102at the same time. In a case where the row number of the rectangular interleaver is 20 (i.e., R=20) and the first decoder104is a quad-core decoder, each decoder core114of the first decoder104is required to decode data bits located at five successive data rows. As the inter-row interleaving is properly configured to ensure that all decoder cores in each decoder core group do not access the same bank simultaneously, the decoder cores114of the first decoder104would have contention-free memory access of the memory device102.

Please refer toFIG. 5in conjunction withFIG. 6for better understanding of the technical features of the present invention.FIG. 5is a diagram illustrating a memory access order of four decoder cores in the first decoder104according to an embodiment of the present invention.FIG. 6is a timing diagram of the parallel decoding operation performed by the four decoder cores in the first decoder104according to an embodiment of the present invention. In this embodiment, the decoder cores114_1and114_3belong to one decoder core group502, and the decoder cores114_2and114_4belong to the other decoder core group504. The decoder core groups502and504take turns to obtain 8 data bits (e.g., soft bits) from the memory device102, where each of the decoder core114_1-114_4is arranged to get 4 data bits when granted to access the memory device102. As shown inFIG. 5, 20 data rows of a data block are stored in 10 memory banks in an inter-row permuted fashion. Hence, when one of the decoder cores114_1-114_4is granted to access the memory device102, two data bits to be decoded in each cycle would be located at the same bank. Due to the pack-4 format employed, each of the decoder cores114_1-114_4is capable of getting the desired 4 data bits in one memory access cycle. As can be seen fromFIG. 6, the decoder core114_1successively gets 4 data bits D00-D03in one cycle between T0and T1, and the decoder core114_3successively gets 4 data bits D20-D23in one cycle between T0and T1. Hence, the decoder core114_1decodes first two data bits D00and D01in one cycle between T0and T1, and decodes last two data bits D02and D03in one cycle between T1and T2. Similarly, the decoder core114_3decodes first two data bits D20and D21in one cycle between T0and T1, and decodes last two data bits D22and D23in one cycle between T1and T2. After the data bits D00-D03have been completely decoded during two cycles, the decoder core114_1successively gets the next 4 data bits D00′-D03′ in one cycle between T2and T3, decodes first two data bits D00′ and D01′ in one cycle between T2and T3, and decodes last two data bits D02′ and D03′ in one cycle between T3and T4. Similarly, after the data bits D20-D23have been completely decoded during two cycles, the decoder core114_3successively gets the next 4 data bits D20′-D23′ in one cycle between T2and T3, decodes first two data bits D20′ and D21′ in one cycle between T2and T3, and decodes last two data bits D22′ and D23′ in one cycle between T3and T4. As each of the decoder cores114_1and114_3of the same decoder core group502gets four data bits in each memory access and decodes two data bits per cycle, the decoder cores114_1and114_3only need to access the memory device102every two cycles. Similarly, as can be seen fromFIG. 6, each of the decoder cores114_2and114_4of the same decoder core group504only need to access the memory device102every two cycles. However, when one decoder core group is accessing the memory device102in a current cycle, the other decoder core group would not access the memory device102because the data bits to be decoded have been fetched in the previous cycle. Thus, with the help of the inter-row permutation applied to the data rows stored in the memory banks, the decoder cores114_1-114_4of the first decoder104would have contention-free memory access of the memory device102. Some examples are provided as below.

In a first case where the number of input bits K meets the criterion: (2281≦K≦2480) or (3161≦K≦3210), the corresponding inter-row permutation patterns for R=20, as shown in above Table 1, are adopted. Suppose that the 19throw and the 20throw (i.e., row18and row19shown inFIG. 5) are dummy rows composed of dummy bits. Hence, four decoder cores114_1-114_4are required to decode data bits of 18 data rows. In this embodiment, the decoder cores114_1and114_3of the decoder core group502are used for computing forward metrics α first, while the decoder cores114_2and114_4of the decoder core group504are used for computing backward metrics β first. In this way, full-trace decoding can be achieved by using the first decoder104. By way of example, the decoder core114_1is configured to sequentially decode five rows including row0to row4, the decoder core114_2is configured to sequentially decode five rows including row8to row4, the decoder core114_3is configured to sequentially decode five rows including row8to row12, and the decoder core114_4is configured to sequentially decode five rows including row17to row13, where the first half of row4is decoded by the decoder core114_1, and the remaining half of row4is decoded by the decoder core114_2, and the first half of row8is decoded by the decoder core114_2, and the remaining half of row4is decoded by the decoder core114_3.

Please refer toFIG. 7in conjunction with the aforementioned Table 2.FIG. 7is a diagram illustrating the relation between data rows and memory banks according to a first embodiment of the present invention. Regarding the decoder core group502, the decoder core114_1needs to access one of a plurality of memory banks, including banks3,4and5; and the decoder core114_3needs to access one of a plurality of memory banks, including banks1,7,8and9. As the memory banks to be accessed by the decoder cores114_1and114_3in the same decoder core group502are mutually exclusive, the decoder cores114_1and114_3would have contention-free memory access of the memory device102. Regarding the decoder core group504, the decoder core114_2needs to access one of a plurality of memory banks, including banks3,6,7and8; and the decoder core114_4needs to access one of a plurality of memory banks, including banks0,1,2and3. As can be seen fromFIG. 7, the decoder core114_2has to access bank3for decoding data bits of row4, and the decoder core114_4has to access bank3for decoding data bits of row15. It should be noted that row4is the fifth data row to be decoded by the decoder core114_2, and row15is the third data row to be decoded by the decoder core114_4. As the difference between the decoding order of row4and the decoding order of row15is not large enough, it is possible that the decoder core114_2starts decoding data bits of row4before the decoder core114_4finishes decoding data bits of row15. To guarantee that the decoder cores114_2and114_4would not access the same memory bank (i.e., bank3) at the same time, the synchronization control between the decoder cores114_2and114_4may be employed. In this way, the decoder cores114_2and114_4also have contention-free memory access of the memory device102.

In an alternative design, the inter-row interleaving is configured to ensure that all decoder cores in each decoder core group do not access the same memory bank simultaneously, where regarding each decoder core group, banks storing data rows to be decoded by one decoder core are not accessed by other decoder core(s). The present invention thus proposes additional row swapping for the row assignment excluding dummy rows. The adjusted distribution of the inter-row permuted rows for different row numbers of the rectangular interleaver is illustrated in the following table.

Compared to above Table 2, Table 3 has row0stored in bank3and row4stored in bank4for R=20 under the condition where (2281≦K≦2480) or (3161≦K≦3210), and has row16stored in bank5and row1stored in bank6for R=20 under the another condition where K=any other value. Please refer toFIG. 8in conjunction with aforementioned Table 3.FIG. 8is a diagram illustrating the relation between data rows and memory banks according to a second embodiment of the present invention. Based on the row assignment as shown in Table 3, the memory banks to be accessed by the decoder cores114_1and114_3in the same decoder core group502are mutually exclusive, and the memory banks to be accessed by the decoder cores114_2and114_4in the same decoder core group502are also mutually exclusive. Such an exclusive memory access design can omit the complex synchronization control between decoder cores in the same decoder core group.

In a second case where the number of input bits K meets the criterion: K=any other value, the corresponding inter-row permutation patterns for R=20, as shown in above Table 1, are adopted. Suppose that the 19th row and the 20th row (i.e., row18and row19shown inFIG. 5) are dummy rows composed of dummy bits. Hence, four decoder cores114_1-114_4are required to decode data bits of 18 data rows. In this embodiment, the decoder cores114_1and114_3of the decoder core group502are used for computing forward metrics a first, while the decoder cores114_2and114_4of the decoder core group504are used for computing backward metrics β first. Similarly, full-trace decoding is achieved by using the first decoder104in this embodiment. By way of example, the decoder core114_1is configured to sequentially decode five rows including row0to row4, the decoder core114_2is configured to sequentially decode five rows including row8to row4, the decoder core114_3is configured to sequentially decode five rows including row8to row12, and the decoder core114_4is configured to sequentially decode five rows including row17to row13, where the first half of row4is decoded by the decoder core114_1, and the remaining half of row4is decoded by the decoder core114_2, and the first half of row8is decoded by the decoder core114_2, and the remaining half of row4is decoded by the decoder core114_3.

Please refer toFIG. 9in conjunction with the aforementioned Table 2.FIG. 9is a diagram illustrating the relation between data rows and memory banks according to a third embodiment of the present invention. The row assignment for R=20 under the condition where K=any other value, as shown in Table 2, is employed. Therefore, regarding the decoder core group502, the decoder core114_1needs to access one of a plurality of memory banks, including banks3,4and5; and the decoder core114_3needs to access one of a plurality of memory banks, including banks0,1,8and9. As the memory banks to be accessed by the decoder cores114_1and114_3in the same decoder core group502are mutually exclusive, the decoder cores114_1and114_3would have contention-free memory access of the memory device102.

Regarding the decoder core group504, the decoder core114_2needs to access one of a plurality of memory banks, including banks1,3,6and7; and the decoder core114_4needs to access one of a plurality of memory banks, including banks2,3,6and8. As can be seen fromFIG. 9, the decoder core114_2has to access bank3for decoding data bits of row4, and the decoder core114_4has to access bank3for decoding data bits of row17. Besides, the decoder core114_2has to access bank6for decoding data bits of row5, and the decoder core114_4has to access bank6for decoding data bits of row16. It should be noted that row4is the fifth data row to be decoded by the decoder core114_2, and row17is the first data row to be decoded by the decoder core114_4. As the difference between the decoding order of row4and the decoding order of row17is large, it is possible that the decoder core114_2starts decoding data bits of row4after the timing that the decoder core114_4finishes decoding data bits of row17. Hence, the decoder cores114_2and114_4would not access the same memory bank (i.e., bank3) at the same time. However, row5is the fourth data row to be decoded by the decoder core114_2, and row16is the second data row to be decoded by the decoder core114_4. As the difference between the decoding order of row5and the decoding order of row16is not large enough, it is possible that the decoder core114_2starts decoding data bits of row5before the decoder core114_4finishes decoding data bits of row16. To guarantee that the decoder cores114_2and114_4would not access the same memory bank (i.e., bank6) at the same time, the synchronization control between the decoder cores114_2and114_4may be employed. In this way, the decoder cores114_2and114_4also have contention-free memory access of the memory device102.

Please refer toFIG. 10in conjunction with the aforementioned Table 3.FIG. 10is a diagram illustrating the relation between data rows and memory banks according to a fourth embodiment of the present invention. The row assignment for R=20 under the condition where K=any other value, as shown in Table 3, is employed. As can be seen fromFIG. 10, the memory banks to be accessed by the decoder cores114_1and114_3in the same decoder core group502are mutually exclusive. Hence, the decoder cores114_1and114_3would have contention-free memory access of the memory device102. Regarding the decoder core group504, the decoder core114_2has to access bank3for decoding data bits of row4, and the decoder core114_4has to access bank3for decoding data bits of row17. It should be noted that row4is the fifth data row to be decoded by the decoder core114_2, and row17is the first data row to be decoded by the decoder core114_4. As the difference between the decoding order of row4and the decoding order of row17is large, it is possible that the decoder core114_2starts decoding data bits of row4after the decoder core114_4finishes decoding data bits of row17. Hence, the decoder cores114_2and114_4would not access the same memory bank (i.e., bank3) at the same time. In this way, the decoder cores114_2and114_4also have contention-free memory access of the memory device102.