Abstract:
A high-speed decoder includes a buffer that includes buffer space for Q encoded data frames, where Q is a rational number greater than or equal to two. An iterative decoder receives the data frames from the buffer, generates a confidence result with each decoding iteration, and completes decoding a data frame when at least one of the number of iterations reaches a predetermined maximum number of iterations and the confidence result is greater than or equal to a predetermined confidence level. The iterative decoder stops decoding the Q data frames after a predetermined total number of iterations that is less than Q times the predetermined maximum number of iterations.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This application claims the benefit of U.S. Provisional Application No. 60/711,164, filed on Aug. 25, 2005. The disclosure of the above application is incorporated herein by reference in its entirety. 

   FIELD 
   The present disclosure relates to iterative decoders in digital communication systems. 
   BACKGROUND 
   In communication systems it is desirable to accurately transmit as much information as possible through a communication channel for a given amount of transmission power. One method of improving the bandwidth in a communication system is to encode the transmitted data with a forward error-correcting code (FEC). The FEC interleaves the data and generates parity data, which is combined with the interleaved data and transmitted through the communication channel. A receiver includes a decoder that uses the parity data to help recover the data. Whether the decoder successfully recovers the data depends on the depth of the interleaving, the amount of parity data, and the characteristics of noise in the communication channel. 
   Referring now to  FIG. 1 , a block diagram is shown of a communication system  10 . A first transceiver  12 - 1  and second transceiver  12 - 2 , collectively referred to as transceivers  12 , communicate with each other via a communication channel  14 . Transceivers  12  include respective physical layer modules (PHY)  16  that directly interface with communication channel  14 . PHYs  16  communicate with FEC encoders  18  and FEC decoders  20 . Hosts  22  generate and receive the data that is processed by FEC encoders  18 , communicated via communication channel  14 , and decoded by FEC decoders  20 . 
   Encoders  18  may employ a FEC such as low-density parity check (LDPC) and/or concatenated codes such as turbo serial-concatenated convolutional codes. Encoders  18  include first, or outer, encoders  26  that encode the data from hosts  22  according to a first codeword. Interleavers  28  interleave encoded data from outer encoders  26  before communicating it to second, or inner, encoders  30 . Inner encoders  30  encode the interleaved data according to a second codeword. Inner encoders  30  then communicate the encoded data to PHYs  16  to be transmitted. 
   Optimal decoding for LDPC and turbo coding is too complicated to be implemented practically. Iterative decoding therefore provides a practical alternative. Iterative decoding is a sub-optimal decoding algorithm with reasonable implementation complexity. Iterative decoding is also referred to as message-parsing since the received message data is parsed between two decoding subsystems. 
   Decoders  20  include first sub-systems  32  that receive the transmitted data from PHYs  16 . First sub-systems  32  communicate decoded data to deinterleavers  34 . First sub-systems  32  can also generate one or more signals  36  that indicate how certain first sub-systems  32  are of the accuracy of the data that was sent to deinterleavers  34 . Second sub-systems  38  receive the deinterleaved data from deinterleavers  34  and decode it. Second subsystems  38  can provide feedback, or soft result,  40  to outer decoders  32  to improve decoding accuracy. 
   Referring now to  FIG. 2  a flow diagram is shown of data as it passes through first sub-systems  32  and second sub-systems  38 . When encoders  18  employ one of the turbo codes, first sub-systems  32  represent first, or outer, decoders and second sub-systems  38  represent second, or inner decoders. When encoders  18  employ one of the LDPCs, first sub-systems  32  represent all check nodes and the second sub-systems  38  represent all bit nodes. 
   Data from PHYs  16  enter first sub-systems  32  to be decoded according to the second codeword. The partially decoded data is communicated to second systems  38  to be decoded according to the first codeword. Second subsystems  38  communicate the soft result to first sub-systems  32  for further decoding. This process repeats until second subsystems  38  generate hard results  42  that are communicated to hosts  22 . The number of iterations through first-subsystems  32  and second sub-systems  38  can be predetermined based on a maximum bit error rate (BER) desired in the hard results  42 . 
   Increasing the number of iterations reduces the BER, i.e. increases the accuracy of the decoded data. However, increasing the number of iterations increases a computational burden on decoders  20 . In order to maintain decoding throughput with the higher number of iterations the computational throughput of decoders  20  must be increased. This can be achieved by increasing a clock frequency of decoders  20 . It should be appreciated however that increasing clock frequencies introduces other issues. These issues include increasing power consumption and/or increasing design complexity due to smaller signal timing margins. There remains a need in the art for a method of increasing the decoding throughput of decoders  20 . 
   SUMMARY 
   A high-speed decoder includes a buffer that includes buffer space for Q encoded data frames, where Q is a rational number greater than or equal to two. An iterative decoder receives the data frames from the buffer, generates a confidence result with each decoding iteration, and completes decoding a data frame when at least one of the number of iterations reaches a predetermined maximum number of iterations and the confidence result is greater than or equal to a predetermined confidence level. The iterative decoder stops decoding the Q data frames after a predetermined total number of iterations that is less than Q times the predetermined maximum number of iterations. 
   In other features the predetermined total number of iterations corresponds with a maximum acceptable error rate in decoding the Q data frames. The high speed decoder further includes a clock that drives the iterative decoder and operates at a clock frequency based on an average number of iterations needed for the confidence result to achieve the predetermined confidence level. The high-speed decoder further includes a second buffer that receives decoded data frames from the iterative decoder. The second buffer includes a buffer space having the same size as the buffer space of the first buffer. 
   In other features a transceiver includes the high-speed decoder and a forward error correction encoder that employs a concatenated code. The high-speed decoder further includes a physical layer module that communicates with an input of the first buffer and that is otherwise compatible with at least one of the Bluetooth standard, Institute of Electrical and Electronics Engineers (IEEE) standard 802.3, 802.3an, 802.11, 802.11a, 802.11b, 802.11g, 802.11h, 802.11n, 802.16, and 802.20. 
   A high-speed decoding method includes buffering Q data frames, where Q is a rational number greater than or equal to two. The method also includes receiving the data frames from the buffering step, iteratively decoding the data frames, generating a confidence result with each decoding iteration, and completing decoding a data frame when at least one of the number of iterations reaches a predetermined maximum number of iterations and the confidence result is greater than or equal to a predetermined confidence level. The iterative decoding step stops decoding the Q data frames after a predetermined total number of iterations that is less than Q times the predetermined maximum number of iterations. 
   In other features the predetermined total number of iterations corresponds with a maximum acceptable error rate in decoding the Q data frames. The decoding method also includes clocking the iterative decoding step at a clock frequency based on an average number of iterations needed for the confidence result to achieve the predetermined confidence level. The high-speed decoding method also includes receiving the decoded data frames from the iterative decoding step and buffering the decoded data frames. The step of buffering the decoded data frames includes maintaining a buffer space having a same size as a buffer space used in the step of buffering Q data frames. The high-speed decoding method also includes receiving the Q data frames according to at least one of the Bluetooth standard, Institute of Electrical and Electronics Engineers (IEEE) standard 802.3, 802.3an, 802.11, 802.11a, 802.11b, 802.11g, 802.11h, 802.11n, 802.16, and 802.20, and communicating the received Q data frames to the buffering step. 
   A high-speed decoder includes buffer means for buffering Q encoded data frames, where Q is a rational number greater than or equal to two. The high-speed decoder also includes iterative decoder means for receiving the data frames from the buffer means, generating a confidence result with each decoding iteration, and completing decoding a data frame when at least one of the number of iterations reaches a predetermined maximum number of iterations and the confidence result is greater than or equal to a predetermined confidence level. The iterative decoder means stops decoding the Q data frames after a predetermined total number of iterations that is less than Q times the predetermined maximum number of iterations. 
   In other features the predetermined total number of iterations corresponds with a maximum acceptable error rate in decoding the Q data frames. The high-speed decoder also includes clock means for driving the iterative decoder means and at a clock frequency based on an average number of iterations needed for the confidence result to achieve the predetermined confidence level. The high-speed decoder also includes second buffer means for receiving decoded data frames from the iterative decoding means. The second buffer means includes a buffer space having the same size as the buffer space of the first buffer means. The high-speed decoder also includes physical layer means for communicating with an input of the first FIFO means and that is otherwise compatible with at least one of the Bluetooth standard, Institute of Electrical and Electronics Engineers (IEEE) standard 802.3, 802.3an, 802.11, 802.11a, 802.11b, 802.11g, 802.11h, 802.11n, 802.16, and 802.20. 
   In still other features, the systems and methods described above are implemented by a computer program executed by one or more processors. The computer program can reside on a computer readable medium such as but not limited to memory, non-volatile data storage and/or other suitable tangible storage mediums. 
   Further areas of applicability of the present disclosure will become apparent from the detailed description provided hereinafter. It should be understood that the detailed description and specific examples, while indicating the preferred embodiment of the disclosure, are intended for purposes of illustration only and are not intended to limit the scope of the disclosure. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present disclosure will become more fully understood from the detailed description and the accompanying drawings, wherein: 
       FIG. 1  is a functional block diagram of a digital communications system of the prior art; 
       FIG. 2  is a flow diagram of an iterative decoding method of the prior art; 
       FIG. 3 . is a functional block diagram of digital communication transceivers with improved decoders; 
       FIG. 4  is a flowchart of an improved iterative decoding method; 
       FIG. 5A  is a functional block diagram of a high definition television; 
       FIG. 5B  is a functional block diagram of a vehicle control system; 
       FIG. 5C  is a functional block diagram of a cellular phone; 
       FIG. 5D  is a functional block diagram of a set top box; and 
       FIG. 5E  is a functional block diagram of a media player. 
   

   DETAILED DESCRIPTION 
   The following description is merely exemplary in nature and is in no way intended to limit the disclosure, its application, or uses. For purposes of clarity, the same reference numbers will be used in the drawings to identify similar elements. As used herein, the term module, circuit and/or device refers to an Application Specific Integrated Circuit (ASIC), an electronic circuit, a processor (shared, dedicated, or group) and memory that execute one or more software or firmware programs, a combinational logic circuit, and/or other suitable components that provide the described functionality. As used herein, the phrase at least one of A, B, and C should be construed to mean a logical (A or B or C), using a non-exclusive logical or. It should be understood that steps within a method may be executed in different order without altering the principles of the present disclosure. 
   Referring now to  FIG. 3 , an improved digital communications system  100  is shown. A first transceiver  102 - 1  and a second transceiver  102 - 2 , collectively referred to as transceivers  102 , communicate through a communications channel  104 . Communications channel  104  can include one or more of wired, fiber-optic, and/or wireless channels. Transceivers  102  can be compliant with at least one of the Institute of Electrical and Electronics Engineers (IEEE) standards 802.3, 802.3an, 802.11, 802.11a, 802.11b, 802.11g, 802.11h, 802.11n, 802.16, and 802.20, and/or the Bluetooth standard published by the Bluetooth Special Interest Group (SIG). The aforementioned standards are hereby incorporated by reference in their entirety. 
   Transceivers  102  include PHYs  106  that provide an interface to the communication channel  104 . PHYs  106  also communicate with encoders  108  and decoder channels  110 . Interface modules  112  provide an interface between hosts  114  and associated encoders  108  and decoder channels  110 . Examples of hosts  114  include various computers, servers, voice-over-internet protocol (VoIP) telephones, digital video servers, digital video displays, and/or other devices. 
   Encoders  108  employ concatenated codes. Decoder channels  110  include input first-in, first-out buffers (FIFOs)  120  and output FIFOs  121  that communicate with respective inputs and outputs of central processing units (CPU)  122 . In some embodiments FIFOs  120 ,  121  include sufficient memory space to buffer  0  data frames received through the communication channel  104 . Q is a real number greater than 2. If N represents a number of bits in each data frame then the buffer memory size is Q*N bits. 
   CPUs  122  are driven by a clock  124  that operates at a clock frequency. The clock frequency is determined based on methods described below and affects power consumption, signal timing tolerances, and operating speed of CPUs  122 . CPUs  122  implement iterative decoders  126  which employ LDPC and/or turbo decoding schemes. 
   Each iterative decoder  126  generates a confidence result  128  with each decoding iteration. CPU  122  compares confidence result  128  to a predetermined value to determine whether iterative decoder  126  has decoded the data frame to a desired degree of accuracy. Iterative decoder  126  continues iteratively decoding the present data frame until the desired degree of accuracy is reached. Iterative decoder  126  stops decoding the present data frame if confidence result  128  does not achieve the predetermined value within a predetermined maximum number of iterations. When iterative decoder  126  stops decoding the present data frame it sends the corresponding decoded data frame to output FIFO  121  and reads the next data frame from input FIFO  120 . When the iterative decoder  126  implements the LDPC scheme then confidence result  128  can be compared to a parity check metric. When iterative decoder  126  implements the turbo-decoder scheme then confidence result  128  can be compared to a generator polynomial. 
   Referring now to  FIG. 4 , a flowchart is shown of a method  200  for determining Q and the frequency of clock  124 . A working example is also provided after the following description of method  200 . Control begins in block  202  and immediately proceeds to block  204 . In block  204  control chooses a target frame error rate (FER) for data frames that are received through channel  104 . Control then proceeds to block  206  and determines a number of iterations, MAX_ITER, of the iterative decoders  126  that would be necessary to achieve the target FER. The frequency of clock  124  is then determined based on MAX_ITER and a frame transmission rate through channel  104 . Control then proceeds to block  208  and selects Q&gt;2. Control then proceeds to block  210  and selects a new clock frequency based on an average number of iterations through iterative decoders  126  that would be necessary to stay within the target FER. Control then exits though block  212 . 
   A working example will now be described. The target FER in block  204  is chosen to be 10 −12 . In this example it is assumed that iterative decoders  126  provide an FER of 10 −5  after three iterations, an FER of 10 −8  after four iterations, and an FER of 10 −12  FER after five iterations. If Q is chosen to be 2, then two consecutive frames can be stored in FIFOs  120  and  121 . One of the consecutive frames has a probability of 10 −8  of needing more than four iterations. The probability of the other frame needing more than three iterations is then 10 −5 . If the frequency of clock  124  decoder clock is selected such that iterative decoder  126  can perform four iterations per frame, then the overall probability of erroneously decoding data due a FIFO overflow of Q consecutive frames is 10 −8 *10 −5 =10 −13 . This means that the frequency of clock  124  can be reduced by 20% due to the reduction from five iterations per frame to four iterations per frame on average. The FIFOs  120  and  121  thereby allow decoder channels  110  to consume less power than other decoder channels that do not use FIFOs  120  and  121 . Similarly, FIFOs  120  and  121  allow decoder channels  110  to process a greater number of frames per unit time for a given frequency of clock  124 . Therefore the disclosed decoder arrangement uses large enough FIFOs such that the frequency of clock  124  can be set for the average number of iterations per frame instead of the maximum number of iterations per frame. 
   Referring now to  FIGS. 5A-5E  various exemplary implementations of the present invention are shown. Referring now to  FIG. 5A , the present invention can be implemented in a high definition television (HDTV)  420 . The present invention may implement and/or be implemented in a wireless local area network (WLAN) interface  429 . The HDTV  420  receives HDTV input signals in either a wired or wireless format and generates HDTV output signals for a display  426 . In some implementations, a signal processing circuit and/or control circuit  422  and/or other circuits (not shown) may process data, perform coding and/or encryption, perform calculations, format data and/or perform any other type of HDTV processing that may be required. 
   The HDTV  420  may communicate with mass data storage  427  that stores data in a nonvolatile manner such as optical and/or magnetic storage devices. The mass data storage  427  may include optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. Mass data storage  427  may include at least one HDD and/or least one DVD. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The HDTV  420  may be connected to memory  428  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The HDTV  420  also may support connections with a WLAN via the WLAN interface  429 . The HDTV  420  also includes a power supply  423 . 
   Referring now to  FIG. 5B , the present invention may be implemented in a WLAN interface  448  of a vehicle  430 . Vehicle  430  includes a powertrain control system  432  that receives inputs from one or more sensors  436  such as temperature sensors, pressure sensors, rotational sensors, airflow sensors and/or any other suitable sensors and/or that generates one or more output control signals  438  such as engine operating parameters, transmission operating parameters, and/or other control signals. 
   The present invention may also be implemented in other control systems  440  of the vehicle  430 . The control system  440  may likewise receive signals from input sensors  442  and/or output control signals to one or more output devices  444 . In some implementations, the control system  440  may be part of an anti-lock braking system (ABS), a navigation system, a telematics system, a vehicle telematics system, a lane departure system, an adaptive cruise control system, a vehicle entertainment system such as a stereo, DVD, compact disc and the like. Still other implementations are contemplated. 
   The powertrain control system  432  may communicate with mass data storage  446  that stores data in a nonvolatile manner. The mass data storage  446  may include optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. Mass data storage  446  may include at least one HDD and/or least one DVD. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The powertrain control system  432  may be connected to memory  447  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The powertrain control system  432  also may support connections with a WLAN via the WLAN interface  448 . The control system  440  may also include mass data storage, memory and/or a WLAN interface (all not shown). The vehicle  430  also includes a power supply  433 . 
   Referring now to  FIG. 5C , the present invention can be implemented in a cellular phone  450  that may include a cellular antenna  451 . The invention may be implemented in a WLAN interface  468 . In some implementations, the cellular phone  450  includes a microphone  456 , an audio output  458  such as a speaker and/or audio output jack, a display  460  and/or an input device  462  such as a keypad, pointing device, voice actuation and/or other input device. Signal processing and/or control circuits  452  and/or other circuits (not shown) in the cellular phone  450  may process data, perform coding and/or encryption, perform calculations, format data and/or perform other cellular phone functions. 
   The cellular phone  450  may communicate with mass data storage  464  that stores data in a nonvolatile manner such as optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The cellular phone  450  may be connected to memory  466  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The cellular phone  450  also may support connections with a WLAN via the WLAN interface  468 . Cellular phone  450  also includes a power supply  453 . 
   Referring now to  FIG. 5D , the present invention can be implemented in a set top box  480 . The present invention may be implemented in a WLAN interface  496  of the set top box  480 . The set top box  480  receives signals from a source such as a broadband source and outputs standard and/or high definition audio/video signals suitable for a display  488  such as a television and/or monitor and/or other video and/or audio output devices. The signal processing and/or control circuits  484  and/or other circuits (not shown) of the set top box  480  may process data, perform coding and/or encryption, perform calculations, format data and/or perform any other set top box function. 
   The set top box  480  may communicate with mass data storage  490  that stores data in a nonvolatile manner. The mass data storage  490  may include optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The set top box  480  may be connected to memory  494  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The set top box  480  also may support connections with a WLAN via the WLAN interface  496 . The set top box  480  includes a power supply  483 . 
   Referring now to  FIG. 5E , the present invention can be implemented in a media player  500 . The present invention may be implemented in a WLAN interface  516  of the media player  500 . In some implementations, the media player  500  includes a display  507  and/or a user input  508  such as a keypad, touchpad and the like. In some implementations, the media player  500  may employ a graphical user interface (GUI) that typically employs menus, drop down menus, icons and/or a point-and-click interface via the display  507  and/or user input  508 . The media player  500  further includes an audio output  509  such as a speaker and/or audio output jack. Signal processing and/or control circuits  504  and/or other circuits (not shown) of the media player  500  may process data, perform coding and/or encryption, perform calculations, format data and/or perform any other media player function. 
   The media player  500  may communicate with mass data storage  510  that stores data such as compressed audio and/or video content in a nonvolatile manner. In some implementations, the compressed audio files include files that are compliant with MP3 format or other suitable compressed audio and/or video formats. The mass data storage may include optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The media player  500  may be connected to memory  514  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The media player  500  also may support connections with a WLAN via the WLAN interface  516 . The media player  500  also includes a power supply  513 . Still other implementations in addition to those described above are contemplated. For example, the WLAN interfaces can be replaced and/or supplemented with wired and/or fiber-optic network interfaces. 
   Those skilled in the art can now appreciate from the foregoing description that the broad teachings of the disclosure can be implemented in a variety of forms. Therefore, while this disclosure includes particular examples, the true scope of the disclosure should not be so limited since other modifications will become apparent to the skilled practitioner upon a study of the drawings, the specification and the following claims.