Abstract:
A data correction apparatus, a data correction method and a tangible machine-readable medium thereof are provided. The data correction method comprises the following steps: receiving a plurality of packets; determining that all of the packets are erroneous packets according to cyclic redundancy check (CRC) information thereof; retrieving any number of pairs among the packets to proceed an exclusive-OR (XOR) logical calculation to generate a plurality of error patterns; obtaining an overall error pattern according to an OR logical calculation of the error patterns; and calculating a correct packet according to one or more of the packets and the overall error pattern.

Description:
This application claims the benefit of priority based on Taiwan Patent Application No. 097148793, filed on Dec. 15, 2008, the contents of which are incorporated herein by reference in their entirety. 
     CROSS-REFERENCES TO RELATED APPLICATIONS 
     Not applicable. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a data correction apparatus, a data correction method and a tangible machine-readable medium thereof. More particularly, the present invention relates to a data correction apparatus, a data correction method and a tangible machine-readable medium thereof that use cyclic redundancy check (CRC) information to calculate a correct packet. 
     2. Descriptions of the Related Art 
     With the aid of network communications, users are able to exchange information, conduct voice communication or even conduct goods transactions. For this reason, networks have become indispensable in the daily life of modern people. Users can upload or download a wide variety of information via networks, and such information is transmitted via the networks in form of data packets. However, due to the noise in the network data transmission channel or communication interference from other data transmissions underway in the networks, errors or even corruptions usually occur in the data packets when being received at the receiving end, thereby causing degradation in the performance of the network communications. 
     To improve this problem, network equipment manufacturers have used the cyclic redundancy check (CRC) mechanism that has been practiced for many years. CRC is a kind of error detection mechanism which has found wide application in media access control (MAC) layers of wired and wireless networks. To use the CRC mechanism, a data transmitting end adds, in the data to be transmitted, a CRC remainder to generate a data packet with a CRC code, and then transmits the resulting data packet with the CRC code. When receiving the data packet with the CRC code, the receiving end checks the packet against the CRC code, and if an error is found in the received data packet, the receiving end will abandon the data packet that is determined to be erroneous. 
     In combination with the aforesaid CRC mechanism for error detection, the receiving end may further employ a retransmission mechanism, e.g., the automatic repeat request (ARQ) or hybrid automatic repeat request (HARQ) framework, to request the transmitting end to retransmit the previously transmitted data packet with the CRC code. In this way, the receiving end can filter out erroneous data packets and acquire the correct data packet through retransmissions, thereby decreasing the error rate of data transmissions in network communications. 
     Unfortunately, in case the network data transmission channel experiences very poor conditions or suffers from very serious communication interference, the data transmitting end has to retransmit the data packet many times to ensure that the correct data packet has been received without error at the receiving end. This is effective in decreasing the error rate of data transmissions, but wastes network bandwidth resources. Accordingly, decreasing both the error rate of data transmissions and usage of network bandwidth resources at the same time in the network communications is still a problem. 
     SUMMARY OF THE INVENTION 
     One objective of the present invention is to provide a data correction apparatus, which comprises a reception module, a determination module, a pattern generating module and a calculation module. The reception module is configured to receive a first packet, a second packet and a third packet. The first packet comprises a plurality of first data bits and CRC information, the second packet comprises a plurality of second data bits and the CRC information, and the third packet comprises a plurality of third data bits and the CRC information. The determination module is configured to determine whether the first packet, the second packet and the third packet are erroneous packets according to the CRC information. When the first packet, the second packet and the third packet are all erroneous packets, the pattern generating module retrieves any number of pairs among each of the first data bits, each of the second data bits and each of the third data bits to perform an XOR logical operation thereon to generate a plurality of error patterns. Then, the pattern generating module further performs an OR logical operation on the plurality of error patterns to generate an overall error pattern. Finally, the calculation module is configured to calculate a correct packet according to the overall error pattern and either the first packet, the second packet or the third packet. 
     Another objective of the present invention is to provide a data correction method, which comprises the following steps: receiving a first packet, wherein the first packet comprises a plurality of first data bits and CRC information; determining that the first packet is an erroneous packet according to the CRC information; receiving a second packet, wherein the second packet comprises a plurality of second data bits and the CRC information; determining that the second packet is an erroneous packet according to the CRC information; receiving a third packet, wherein the third packet comprises a plurality of third data bits and the CRC information; determining that the third packet is an erroneous packet according to the CRC information; retrieving any number of pairs among each of the first data bits, each of the second data bits and each of the third data bits to perform an XOR logical operation thereon to generate the same number of error patterns as the erroneous packets; performing an OR logical operation on the error patterns to generate an overall error pattern; and calculating a correct packet according to the overall error pattern and either the first packet, second packet or the third packet. 
     This invention also provides a tangible machine-readable medium storing a computer program product for the data correction apparatus to perform the data correction method. 
     According to the above description, the data correction apparatus, the data correction method and the tangible machine-readable medium thereof of the present invention further retrieves information of each bit in the packets that are determined to be erroneous to correct and calculate a correct packet. In this way, the present invention remarkably reduces the retransmissions of packets and consequently the usage of network bandwidth resources, thereby rendering the use of the network bandwidth resources more efficient. 
     The detailed technology and preferred embodiments implemented for the subject invention are described in the following paragraphs accompanying the appended drawings for people skilled in this field to well appreciate the features of the claimed invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic view of a first embodiment of the present invention; 
         FIG. 2  is a flowchart of a second embodiment of the present invention; 
         FIG. 3  is a schematic view of a third embodiment of the present invention; and 
         FIG. 4  is a flowchart of a fourth embodiment of the present invention. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     In the following description, the present invention will be explained with reference to embodiments thereof. However, these embodiments are described only for purposes of illustration but not limitation. It should be appreciated that in the following embodiments and attached drawings, elements unrelated to the present invention are omitted from depiction; and the dimensional relationships among the individual elements depicted in the attached drawings are only for ease of understanding but not to limit the actual scales. 
       FIG. 1  depicts a first embodiment of the present invention, which is a data correction apparatus  1 . The data correction apparatus  1  may be deployed at a receiving end of a wired or wireless communication system (not shown) with ARQ/HARQ or spatial multiplexing scheme. The data correction apparatus  1  comprises a reception module  11 , a determination module  12 , a calculation module  13 , a pattern generating module  14  and a transmission module  15 . The calculation module  13  comprises a packet generating unit  13   a . The determination module  12  further comprises a remainder calculation unit  12   a  and a remainder determination unit  12   b.    
     When a transmitting end of the wired/wireless communication system transmits the data packet to the data correction apparatus  1  at the receiving end, the transmitting end first generates a correct packet with a CRC code according to the conventional CRC mechanism. For example, if a bit string of the data packet to be transmitted is [1000], then through the CRC mechanism, the transmitting end can perform a calculation according to a generation polynomial (a bit string of which is [101]) to learn that a bit string of the correct packet with both the data packet and the CRC information is [100,011]. The correct packet [100,011] comprises a plurality of data bits and the CRC information. Then, the transmitting end transmits the correct packet [100,011] to the data correction apparatus  1  at the receiving end. 
     The remainder generating unit  12   a  of the determination module  12  comprises one or more CRC circuits (not shown), and the remainder determination unit  12   b  comprises one or more determination circuits (not shown). It should be appreciated that, in terms of structures and operations, both the remainder generating unit  12   a  and the remainder determination unit  12   b  of the determination module  12  are just the same as the conventional standard hardware circuits that implement the CRC mechanism. The present invention has no limitation on the number of CRC circuits included in the generating unit  12   a ; similarly, the present invention has no limitation on the number of determination circuits included in the determination unit  12   b . Rather, those of ordinary skill in the art may arrange an appropriate number of such circuits depending on the practical needs, and thus, this will not be further described herein. 
     Very poor channel conditions and interference from other communication signals may cause an erroneous packet to be received at the receiving end. In particular, when receiving a first packet  101   p  (a bit string of which is [100,111]), the reception module  11  transmits the first packet  101   p  ([100,111]) to the remainder generating unit  12   a  of the determination module  12 . The remainder generating unit  12   a  then calculates a first CRC remainder  101   r  according to the aforesaid generation polynomial [101] and the first packet  101   p  [100,111]. More specifically, by using the first packet  101   p  [100,111] as a dividend and the generation polynomial [101] as a divisor, the remainder generating unit  12   a  performs a binary division operation to obtain a result of the first CRC remainder  101   r  (a bit string of which is [100]). 
     Thereafter, the remainder generating unit  12   a  transmits the first CRC remainder  101   r  [100] to the remainder determination unit  12   b , which then determines whether the first CRC remainder  101   r  [100] is equal to zero. Because the first CRC remainder  101   r  [100] calculated previously is not equal to zero, the determination module  12  determines that the first packet  101   p  [100,111] is an erroneous packet, and the transmission module  15  transmits a reception failure message  161  to the transmitting end to request retransmission of the correct packet [100,011]. Meanwhile, the remainder generating unit  12   a  transmits the first packet  101   p  [100,111] to the pattern generating module  14  to be stored therein. 
     After the transmitting end retransmits the aforesaid correct packet [100,011], the reception module  11  receives a second packet  102   p  (a bit string of which is [100,001]), which comprises a plurality of second data bits and the CRC information. Like the processing of the first packet  101   p  [100,111], the determination module  12  calculates and determines whether the second packet  102   p  [100,001] is an erroneous packet according to the CRC information. In particular, the second packet  102   p  [100,001] is transmitted to the remainder generating unit  12   a  where a calculation is made according to the generation polynomial [101] to obtain a second CRC remainder  102   r  (a bit string of which is [11]). Next, the remainder generating unit  12   a  transmits the second CRC remainder  102   r  [11] to the remainder determination unit  12   b , which determines whether the second CRC remainder  102   r  [11] is equal to zero. Because the second CRC remainder  102   r  [11] is not equal to zero, the second packet  102   p  [100,001] is also determined to be an erroneous packet. Then, the transmission module  15  transmits another reception failure message  162  to the transmitting end to request retransmission of the correct packet [100,011]. Meanwhile, the remainder generating unit  12   a  transmits the second packet  102   p  [100,001] to the pattern generating module  14  to be stored therein. 
     According to the first packet  101   p  [100,111] and the second packet  102   p  [100,001] previously stored, the pattern generating module  14  retrieves each of the first data bits of the first packet  101   p  [100,111] and each of the second data bits of the second packet  102   p  [100,001] to perform an XOR logical operation thereon to obtain a first error pattern  131  (a bit string of which is [000,110]). In the first error pattern  131  [000,110], bits with a value of [1] represent bits where the first packet  101   p  [100,111] is different from the second packet  102   p  [100,001]. In other words, in the first error pattern  131  [000,110], bits with a value of [1] represent bits where an error arises in the first packet  101   p  [100,111] and the second packet  102   p  [100,001]. 
     As the transmission module  15  transmits the reception failure message  162  to the transmitting end to request retransmission of the correct packet [100,011], the transmitting end retransmits the correct packet after receiving the reception failure message  162 . Afterwards, the reception module  11  receives a third packet  103   p  (a bit string of which is [100,100]), which comprises a plurality of third data bits and the CRC information. Similar to what was described in connection with the first packet  101   p  [100, 111] and the second packet  102   p  [100,001], the determination module  12  determines whether the third packet  103   p  [100,100] is an erroneous packet according to the CRC information. In particular, the third packet  103   p  [100,100] is transmitted to the remainder generating unit  12   a  where calculation is made according to the generation polynomial [101] to obtain a third CRC remainder  103   r  (a bit string of which is [01]). Next, the remainder generating unit  12   a  transmits the third CRC remainder  103   r  [01] to the remainder determination unit  12   b , which determines whether the third CRC remainder  103   r  [01] is equal to zero. Because the third CRC remainder  103   r  [01] is still not equal to zero, the third packet  103   p  [100,100] is also determined to be an erroneous packet. Meanwhile, the remainder generating unit  12   a  transmits the third packet  103   p  [100,100] to the pattern generating module  14  to be stored therein. 
     It should be particularly noted herein that the present invention is not limited to use of the CRC error detection approach to determine whether the first packet  101   p , the second packet  102   p  or the third packet  103   p  is an erroneous packet. Rather, depending on the practical needs, those of ordinary skill in the art may choose other error detection approaches to determine whether the first packet  101   p , the second packet  102   p  or the third packet  103   p  is an erroneous packet and, therefore, this will not be further described herein. 
     From the first packet  101   p  [100,111], the second packet  102   p  [100,001] and the third packet  103   p  [100,100] previously stored, the pattern generating module  14  retrieves each data bit of two of the packets to perform a further XOR logical operation thereon to obtain a second error pattern. In this embodiment, the pattern generating module  14  retrieves each of the first data bits of the first packet  101   p  [100,111] and each of the third data bits of the third packet  103   p  [100,100] to perform an XOR logical operation thereon to obtain a second error pattern  132  (a bit string of which is [000,011]). Likewise, in the second error pattern  132  [000,011], bits with a value of [1] represent bits where the first packet  101   p  [100,111] is different from the third packet  103   p  [100,100]. In other words, in the second error pattern  132  [000,011], bits with a value of [1] represent bits where an error arises in the first packet  101   p  [100,111] and the third packet  103   p [ 100,100]. 
     Thereafter, by performing an OR logical operation on the first error pattern  131  [000,110] and the second error pattern  132  [000,011], the pattern generating module  14  calculates all erroneous bits in the first packet  101   p  [100,111], the second packet  102   p  [100,001] and the third packet  103   p  [100,100] to generate a third error pattern  133  (a bit string of which is [000,111]). 
     Afterwards, the packet generating unit  13   a  generates a plurality of target packets according to the third error pattern  133  [000,111] and either the first packet  101   p [ 100,111], the second packet  102   p [ 100,001] or the third packet  103   p  [100,100]. In this embodiment, the packet generating unit  13   a  generates eight target packets according to the first packet  101   p  [100,111] and the third error pattern  133  [000,111], namely,  151   p  [100,000],  152   p [ 100,001],  153   p  [100,010],  154   p [ 100,011],  155   p [ 100,100],  156   p [ 100,101],  157   p  [100,110] and  158   p  [100,111]. 
     The remainder generating unit  12   a  receives these target packets  151   p ,  152   p , . . . ,  158   p  and, according to the generation polynomial [101], calculates target CRC remainders  151   r  [10],  152   r  [11],  153   r  [100],  154   r  [0],  155   r  [01],  156   r  [10],  157   r  [11] and  158   r  [100] corresponding to the target packets  151   p ,  152   p , . . . ,  158   p  respectively. Then, the remainder determination unit  12   b  receives the target CRC remainders  151   r ,  152   r , . . . ,  158   r  and sequentially determines whether each of them is equal to zero. 
     Because the target CRC remainder  154   r  [0] is equal to zero, the remainder determination unit  12   b  determines that the target packet  154   p  [100,011] corresponding to the target CRC remainder  154   r  [0] is the correct packet, thus completing the data correction method of the present invention. 
     If none of the aforesaid target CRC remainders is equal to zero, the transmission module  15  retransmits another reception failure message to the transmitting end to request retransmission of the correct packet [100,011], and operations described above are repeated again. In more detail, if the receiving end receives S erroneous packets in total, the pattern generating module  14  only needs to retrieve (S-1) pairs of erroneous packets and performs an XOR logical operation on the data bits of each pair of erroneous packets to obtain (S-1) error patterns. Then, an OR logical operation is performed on the error patterns to generate an error pattern for calculating the target packets. 
     For example, when the receiving end receives five erroneous packets E 1 , E 2 , E 3 , E 4  and E 5 , the error pattern can be calculated through (E 1  XOR E 2 ) OR (E 2  XOR E 3 ) OR (E 3  XOR E 4 ) OR (E 4  XOR E 5 ), or through (E 1  XOR E 2 ) OR (E 1  XOR E 3 ) OR (E 1  XOR E 4 ) OR (E 1  XOR E 5 ). The packet generating unit  13   a  then calculates each of the target packets, according to the error pattern for calculating the target packets, via one or more of the five erroneous packets E 1 , E 2 , E 3 , E 4  and E 5 . Based on the above description, those of ordinary skill in the art may calculate the error patterns and the target packets according to a different number of erroneous packets and calculate the correct packet through an exhaustive algorithm according to the target packets, and therefore, this will not be further described herein. 
       FIG. 2  depicts a second embodiment of the present invention, which is a data correction method. This data correction method is adapted for a data correction apparatus, e.g., the data correction apparatus  1  described in the first embodiment. The data correction apparatus  1  may be deployed at a receiving end of a wired or wireless communication system (not shown) with an ARQ/HARQ or spatial multiplexing scheme. More specifically, the data correction method of the second embodiment may be implemented by a tangible machine-readable medium. When the tangible machine-readable medium is loaded into the data correction apparatus  1  via a computer and a plurality of codes incorporated in the computer program product are executed, the data correction method of the second embodiment can be accomplished. This computer program product may be stored in a tangible machine-readable medium, such as a read only memory (ROM), a flash memory, a floppy disk, a hard disk, a compact disk, a mobile disk, a magnetic tape, a database accessible to networks, or any other storage media with the same function and well known to those skilled in the art. 
     The second embodiment comprises the following steps. Initially, step  201  is executed to receive a plurality of packets, for example, the first packet, the second packet and the third packet described in the first embodiment. The first packet comprises a plurality of first data bits and a CRC information; the second packet comprises a plurality of second data bits and the CRC information; and the third packet comprises a plurality of third data bits and the CRC information. Then, step  202  is executed to determine whether one of the packets is a correct packet according to the CRC information. More particularly, by using the first packet, the second packet and the third packet as a dividend respectively and a generation polynomial as a divisor, a binary division operation is performed to obtain a first CRC remainder, a second CRC remainder and a third CRC remainder respectively. If the first CRC remainder, the second CRC remainder or the third CRC remainder is equal to zero, this means that one of the packets is the correct packet. Then, step  203  is executed to transmit another packet. 
     On the other hand, if none of the CRC remainders (i.e., the first CRC remainder, the second CRC remainder and the third CRC remainder) is equal to zero in step  202 , this means that all these packets are erroneous. Then, step  204  is executed to determine whether at least two of the packets are retransmitted. If all the packets are independent packets unrelated to each other, step  205  is executed to transmit a reception failure message. 
     Because both the second packet and the third packet are retransmitted packets, step  206  is executed to generate a plurality of error patterns according to the packets, e.g., the first error pattern, the second error pattern and the third error pattern described in the first embodiment. Afterwards, step  207  is executed to generate a plurality of target packets according to the error patterns and one or more of the packets. Next, step  208  is executed to calculate a respective target CRC remainder of each of the target packets, and step  209  is executed to determine whether one of the target CRC remainders is equal to zero. 
     If it is determined in step  209  that one of the target CRC remainders is equal to zero, step  210  is then executed to set the target packet corresponding to the target CRC remainder to be a correct packet. Next, step  203  is executed to transmit another packet. Otherwise, if it is determined in step  208  that none of the target CRC remainders is equal to zero, this data correction method returns to step  205  to transmit a reception failure message anew to request the retransmission of the packet by the transmitting end. 
     In addition to the aforesaid steps, the second embodiment can also execute the operations and functions set forth with respect to the data correction apparatus  1  of the first embodiment. The method in which the second embodiment executes these operations and functions will be readily appreciated by those of ordinary skill in the art based on the explanation of the first embodiment and, thus, will not be further described herein. 
       FIG. 3  depicts a third embodiment of the present invention, which is a data correction apparatus  3 . The data correction apparatus  3  comprises a reception module  11 , a determination module  12 , a calculation module  33 , a pattern generating module  14  and a transmission module  15 . The calculation module  33  comprises a vector processing unit  33   a  and a logical processing unit  33   b , and the determination module  12  comprises a remainder generating unit  12   a  and a remainder determination unit  12   b . This embodiment differs from the first embodiment in the way in which the correct packet is calculated. It should be appreciated that elements bearing the same reference numerals as those of  FIG. 1  have already been described in the first embodiment, and thus will not be further described herein. 
     In reference to  FIG. 3 , as in the first embodiment, the reception module  11  receives the first packet  101   p  [100,111], the second packet  102   p  [100,001] and the third packet  103   p  [100,100] respectively, and the remainder generating unit  12   a  calculates a first CRC remainder  101   r  [100], a second CRC remainder  102   r  [11] and a third CRC remainder  103   r  [01] corresponding thereto respectively according to the generation polynomial [101]. Then, the remainder determination unit  12   b  determines that the first packet  101   p , the second packet  102   p  and the third packet  103   p  are all erroneous packets. The transmission module  15  transmits reception failure messages  161 ,  162  to the transmitting end. The pattern generating module  14  calculates a third error pattern  133  [000,111] according to the following operation: (the first packet  101   p  XOR the second packet  102   p ) OR (the first packet  101   p  XOR the third packet  103   p ). 
     An erroneous packet may be considered as a result of performing an operation on the correct packet and an error pattern vector, so the correct packet can be deduced if the error pattern vector is known. For example, the first packet  101   p  [100,111] may be represented as a result of performing an XOR logical operation on the correct packet [100,011] and the error pattern vector [000,100], so if the error pattern vector [000,100] is obtained, the correct packet can be derived according to the first packet  101   p.    
     As can be seen from the first embodiment, the third error pattern  133  is calculated according to the first packet  101   p , the second packet  102   p  and the third packet  103   p . Therefore, the third error pattern  133  is linearly correlated to the error pattern vector corresponding to the first packet  101   p , the second packet  102   p  or the third packet  103   p . For example, assuming that the third error pattern  133  may be represented as a vector e*=b 1 +b 2 + . . . b m  (b 1 , b 2 , . . . , b m  each represent a unit vector respectively), then the error pattern vector e 1  corresponding to the first packet  101   p  can be represented as a linear relational expression: e 1 =c 1 b 1 +c 2 b 2 + . . . +c m b m  (c 1 , c 2 , . . . , c m  each represent a scalar). Accordingly, this embodiment calculates the error pattern vector according to the following formula: 
     where m represents 
                 [           h   11           h   12         …         h     1   ⁢   m             ]     ⁡     [           c   1               c   2             ⋮             c   m           ]       =   r         
[1] in an error pattern vector (e.g., the third error pattern  133 ), r represents a vector of the CRC remainders of the erroneous packets (e.g., the first CRC remainder  101   r , the second CRC remainder  102   r  or the third CRC remainder  103   r ), (c 1 c 2  . . . c m ) T  represents a vector of scalars associated with the error pattern vectors, and h 11 , h 12 , . . . , h 1m  represent a vector of remainders associated with the error patterns (e.g., the third error pattern  133 ) and the generation polynomial respectively.
 
     From the perspective of linear algebra, the third error pattern  133  [000,111] can be represented as a polynomial of X 2 +X+1 which, in turn, can be represented by an inner product of a vector (X 5 X 4 X 3 X 2 X1) and a vector (000111) T . Hereinbelow, a vector (000111) T  is used to represent the vector e* of the third error pattern  133 . Similarly, a vector (101) T  is used to represent the vector of the generation polynomial [101], a vector (100) T  is used to represent the first CRC remainder  101   r  [100], a vector (011) T  is used to represent the second CRC remainder  102   r  [11], and a vector (001) T  is used to represent the third CRC remainder  103   r  [01]. It should be understood that what is described above may all be readily understood by those of ordinary skill in the art and thus will not be further described herein. 
     The vector processing unit  33   a  has the vector e* of the third error pattern  133  represented as at least one vector. In other words, (000111) T =(000001) T +(000010) T +(000100) T , where b 1 =(000001) T , b 2 =(000010) T  and b 3 =(000100) T  are all unit vectors. Also, for example, the error pattern vector e 1  corresponding to the first packet  1001   p  can be represented as c 1 b 1 +c 2 b 2 +c 3 b 3 . Next, by using the unit vectors b 1 , b 2 , b 3  as a dividend respectively and the generation polynomial vector (101) T  as a divisor, the vector processing unit  33   a  derives the remainder vectors h 11 , h 12 , . . . , h 1m  thereof respectively. It should be emphasized that, [h 11  h 12  . . . h 1m ] is not necessarily a square matrix. For example, if CRC-32 (i.e., the CRC remainder it corresponds to has 32 bits) is used as the generation polynomial and the third error pattern  133  has three bits [1], then [h 11 , h 12 h 13 ] is a 32×3 matrix. 
     This embodiment will use the first packet  101   p  and the error pattern vector e 1  thereof to calculate the correct packet; however, upon reviewing the description of this embodiment, those of ordinary skill in the art may also use the second packet  102   p  and the error pattern vector thereof, or the third packet  103   p  and the error pattern vector thereof to calculate the correct packet. In this embodiment, m=3, and the remainder vectors derived by the vector processing unit  33   a  are h 11 =(001) T , h 12 =(010) T  and h 13 =(100) T  respectively. Meanwhile, r=(100) T  (the vector of the first CRC remainder  101   r  [100]). Thus, by substituting the values of this embodiment, the aforesaid formula is simplified as: 
     
       
         
           
             
               
                 [ 
                 
                   
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                   
                   
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                   
                   
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                   
                 
                 ] 
               
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         c 
                         1 
                       
                     
                   
                   
                     
                       
                         c 
                         2 
                       
                     
                   
                   
                     
                       
                         c 
                         3 
                       
                     
                   
                 
                 ] 
               
             
             = 
             
               [ 
               
                 
                   
                     1 
                   
                 
                 
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                 
               
               ] 
             
           
         
       
     
     There are a number of approaches to calculate (c 1 c 2 c 3 ) T  in the prior art, such as the pseudo inverse approach, the Gaussian elimination approach and etc. In this embodiment, at least one error pattern is generated according to the remainder vectors h 11 , h 12 , h 13  and the vector r of the first CRC remainder  101   r , and an intersection operation is performed on the error patterns to obtain an error pattern vector e 1 . 
     In particular, three equations can be derived from the above formula through observation, namely, c 3 =1, c 2 =0 and c 1 =0 respectively. For c 3 =1, the vector processing unit  33   a  generates an error pattern S 1 ={(c 1 c 2 c 3 ) T =(001) T , (011) T , (101) T , (111) T }. Next, for c 2 =0, the vector processing unit  33   a  generates an error pattern S 2 ={(c 1 c 2 c 3 ) T =(001) T , (101) T , (100) T , (000) T }, and for c 1 =0, the vector processing unit  33   a  generates an error pattern S 3 ={(c 1 c 2 c 3 ) T =(001) T , (011) T , (010) T , (000) T }. Afterwards, the vector processing unit  33   a  performs an intersection operation on the error patterns S 1 , S 2 , S 3  to obtain (c 1 c 2 c 3 ) T =(001), which means that the error pattern vector corresponding to the first packet  101   p  is e 1 =c 1 (000001) T +c 2 (000010) T +c 3 (000100) T =(000100) T . The vector processing unit  33   a  then transmits the error pattern vector e 1  to the logical processing unit  33   b . Then, the logical processing unit  33   b  performs an XOR logical operation on the error pattern vector (000100) T  and the vector of the first packet  101   p  to obtain a vector (100011) T  of the correct packet. In other words, the correct packet is [100,011]. If, subsequent to the intersection operation, the vector processing unit  33   a  still fails to solve the (c 1 c 2 c 3 ) T , the transmission module  15  will a new retransmission request. 
     In a preferred example, this embodiment may further use a deletion approach. In particular, the vector processing unit  33   a  initially calculates the error pattern S 1 ={(c 1 c 2 c 3 ) T =(001) T , (011) T , (101) T , (111) T }. Next, the vector processing unit  33   a  substitutes the error pattern S 1  into the second equation c 2 =0 to delete impossible solutions thereof, thereby yielding the error pattern S 2 ={(c 1 c 2 c 3 ) T =(001) T , (101) T }. Finally, the vector processing  33   a  substitutes the error pattern S 2  into the equation c 1 =0 to delete impossible solutions thereof, thereby yielding the error pattern S 3 ={(c 1 c 2 c 3 ) T =(001) T }. 
     When there are too many possibilities for (c 1 c 2 c 3 ) T , the deletion approach can delete impossible combinations rapidly. In other words, for an error pattern with many bits of [1], the deletion approach only needs to generate a single set of error patterns and then substitute the error patterns thereof into other equations to delete erroneous combinations therefrom. This saves more calculation time as compared to other solutions. Because the number of rows that the deletion approach observes increases, the number of erroneous bit combinations that can be deleted increases exponentially, so it is possible to shorten the time of finding out the correct packet by using the deletion approach in combination with an appropriate data structure (e.g., a tree structure). 
       FIG. 4  is a fourth embodiment of the present invention, which is a data correction method. This data correction method is adapted for a data correction apparatus, e.g., the data correction apparatus  3  described in the third embodiment. The data correction apparatus  3  may be deployed at a receiving end of a wired or wireless communication system (not shown) with an ARQ/HARQ or spatial multiplexing scheme. More specifically, the data correction method of the fourth embodiment may be implemented by a tangible machine-readable medium. When the tangible machine-readable medium is loaded into the data correction apparatus  3  via a computer and a plurality of codes incorporated in the computer program product are executed, the data correction method of the fourth embodiment can be accomplished. This computer program product may be stored in a tangible machine-readable medium, such as a read only memory (ROM), a flash memory, a floppy disk, a hard disk, a compact disk, a mobile disk, a magnetic tape, a database accessible to networks, or any other storage media with the same function and well known to those skilled in the art. 
     The fourth embodiment comprises the following steps. Initially, step  401  is executed to receive a plurality of packets, for example, the first packet, the second packet and the third packet described in the third embodiment. The first packet comprises a plurality of first data bits and a CRC information; the second packet comprises a plurality of second data bits and the CRC information; and the third packet comprises a plurality of third data bits and the CRC information. Then, step  402  is executed to determine whether one of the packets is a correct packet according to the CRC information. More particularly, by using the first packet, the second packet and the third packet as a dividend respectively and a generation polynomial as a divisor, a binary division operation is performed to obtain a first CRC remainder, a second CRC remainder and a third CRC remainder respectively. If either the first CRC remainder, the second CRC remainder or the third CRC remainder is equal to zero, this means that one of the packets is the correct packet. Then, step  403  is executed to transmit another packet. 
     On the other hand, if none of the CRC remainders (i.e., the first CRC remainder, the second CRC remainder and the third CRC remainder) is equal to zero in step  402 , this means that all these packets are erroneous. Then, step  404  is executed to determine whether at least two of the packets are retransmitted ones. If all the packets are independent packets unrelated to each other, step  405  is executed to transmit a reception failure message. 
     Because both the second packet and the third packet are retransmitted packets in the third embodiment, step  406  is executed to generate a plurality of error patterns according to the packets, e.g., the third error pattern as described in the third embodiment. Afterwards, step  407  is executed to represent the last generated error pattern (e.g., the third error pattern) as at least one unit vector, e.g., the three unit vectors b 1 , b 2 , b 3  described in the third embodiment. Next, step  408  is executed to calculate at least one remainder vector (e.g., the remainder vector h 11 , h 12 , h 13  as described in the third embodiment) by using the unit vectors obtained in step  407  as a dividend respectively and a generation polynomial as a divisor. Thereafter, step  409  is executed to determine whether at least one error pattern vector can be obtained according to the remainder vector and one or more of the first CRC remainder, the second CRC remainder and the third CRC remainder. 
     More specifically, by substituting the remainder vector and one or more of the first CRC remainder, the second CRC remainder and the third CRC remainder into the formula described in the third embodiment, the error pattern vectors c 1 , c 2 , c 3  are calculated, the detailed calculation process of which has been described in the third embodiment. If step  409  fails to obtain an error pattern vector, step  405  is executed to transmit a reception failure message. Otherwise, if at least one error pattern vector is generated in step  409 , then according to the error pattern vector, step  410  is executed to perform an XOR logical operation on the error pattern vector and the first, the second or the third packet to obtain the correct packet. Afterwards, this data correction method returns to step  403  to transmit another packet. 
     In addition to the aforesaid steps, the fourth embodiment can also execute the operations and functions set forth with respect to the data correction apparatus  3  of the third embodiment. The methods in which the fourth embodiment executes these operations and functions will be readily appreciated by those of ordinary skill in the art based on the explanation of the third embodiment and, thus, will not be further described herein. 
     According to the above description, the data correction apparatus, the data correction method and the tangible machine-readable medium thereof of the present invention perform a varied number of XOR logical operations and OR logical operations according to the information of data bits of erroneous packets to generate an error pattern. Then, data correction is performed according to the error pattern and the original packet. In this way, the present invention is able to reduce retransmissions of packets to increase the utilization factor of the network bandwidth resources while also decreasing the error rate of data transmissions. 
     The above disclosure is related to the detailed technical contents and inventive features thereof. People skilled in this field may proceed with a variety of modifications and replacements based on the disclosures and suggestions of the invention as described without departing from the characteristics thereof. Nevertheless, although such modifications and replacements are not fully disclosed in the above descriptions, they have substantially been covered in the following claims as appended.