Process for the transmission in blocks of digital information words with error correction capability

• US 4,744,086 A
• Filed: 06/04/1986
• Issued: 05/10/1988
• Est. Priority Date: 06/05/1985
• Status: Expired due to Fees

• Current Assignee: Etablissement Public de Diffusion DIT "Telediffusion de France"
• Original Assignee: Etablissement Public de Diffusion DIT "Telediffusion de France"
• Inventors: Maillard, Michel, Komly, Alain, Weisser, Alain, Viallevieille, Alain
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US06/870,703
• Time in Patent Office: 706 Days
• Field of Search: 371/38, 371/39, 371/40
• US Class Current: 714/762
• CPC Class Codes: G11B 20/1809 by interleaving
• CPC Class Codes: H03M 13/13 Linear codes

Abstract

The invention relates to a process for the transmission in blocks of digital information words with a correction capability. This process consists of transmitting in blocks digital information words, each information word having a length of n₁ bits, in which with each sequence of n₂ -k (n₂ >k) of consecutive information words are associated k redundancy words of n₁ bits each in which, for each order i (1<i<n₂), the k bits of order i of the redundancy words are redundancy bits in accordance with a Hamming code (n₂ 0k, k). For each set of n₂ linked words, each word is transmitted while being protected by an error detecting code. Several sets of linked words can be interlaced. The words of the same order or rank of each set form a group and the groups can be formed by frames.

Claims

1. A process for the transmission in blocks of digital information words, each word having a length of n₁ bits, in which n₁ is an integer, said process comprising successively adding to the information words to be transmitted words of an error correcting code and words of an error detecting code, wherein the error correcting code is a Hamming code by means of which k redundancy words are added to each sequence of n₂ -k, n₂ being an integer greater than k, consecutive informtion words, said n₂ -k information words forming with the K redundancy words a set of words called the linked set, each redundancy word having n₁ bits and, for each order i, in which 1≦

i≦

n, the k bits of order i of the redundancy words are redundancy bits of the n₂ -k bits of order i of the n₂ -k information words, said coding being performed by Hamming matrix, whose column vectors are chosen in such a way as to permit the correction of a given subset of possible errors and the error detecting code is applied to sequences of information words or to sequences of redundancy words, the words of a same sequence belonging to different linked sets, each transmitted block comprising a plurality of sequences of n₂ -k information words and the associated error detecting and correcting code words.

2. A process according to claim 1, wherein an extended Hamming code is used.

3. A process according to claim 1, wherein, for producing the k redundancy bits associated with the n₂ -k information bits, use is made of a Hamming matrix with n₂ and k rows, whereof all the column vectors are of uneven parity.

4. A process according to claim 1, wherein, for producing the k redundancy bits associated with n₂ -k information bits, use is made of a Hamming matrix with n₂ columns and k rows, whereof any sequence of k consecutive column vectors forms a linearly independent system.

5. A process according to claim 1, wherein for producing the k redundancy bits associated with n₂ -k information bits, use is made of a Hamming matrix with n₂ columns and k rows, whereof any sequence of k vectors of indexes i, i+P, i+2P, . . . , i+(k-1)P, in which i,P are integers and i+(k-1)P≦

n₂, forms a linearly independent system.

6. A process according to claim 5 for recording a block on an information medium comprising P parallel recording tracks, wherein the n₂ words of a linked set are distributed over the P tracks, so that the words recorded on the same track are associated with column vectors of the Hamming matrix forming a linearly independent system.

7. A process according to claim 1, wherein, after associating k redundancy words with n₂ -k information words for forming a set of linked words, the words of n₃ linked sets are interlaced to form a transmission block constituted by n₂, each group containing one word of each linked set and at least one error detecting code.

8. A process according to claim 7, wherein the block contains even information words and uneven information words and the groups containing redundancy words are placed in the center of the block, between the groups containing the even information words and the groups containing the uneven information words.

9. A process according to claim 8, wherein each word of a linked set is contained in a frame, each frame comprising a synchronization word, at least one information or redundancy word and an error detecting code.

10. A process according to claim 9 for recording a block on an information medium comprising P parallel tracks, each group of said block comprising f frames, in which f is prime to the number of tracks P, wherein the n₂ words of a linked set are distributed over P tracks, so that the words recorded on the same track are associated with column vectors of the Hamming matrix forming a linearly independent system and wherein the block is recorded frame by frame, the frames of each set of P consecutive frames of the block being placed in parallel on the P tracks.

11. A process according to claim 1, wherein additionally, on reception, determination takes place of the validity of each information or redundancy bit linked with the error detecting codes associated with the information or redundancy words and for each set of n₂ linked bits, the syndrome associated with said set is calculated and from said syndrome and the validity informations relative to each bit is calculated an error vector related to the Hamming code used and each vector of n₂ -k bits received is corrected by said error vector.

12. A process according according to claim 11, wherein, for calculating the error vector of a vector of n₂ -k linked bits, a reduced matrix (H'"'"') constituted by the column vectors of the Hamming matrix (H) used on transmission is defined and whereof the orders are equal to those of the linked bits invalidated by the error detecting codes and from this is deduced another matrix (H'"'"'^-1, H"), such that the product of said other matrix by the syndrome is equal to the error vector.

13. A process according to claim 11, wherein, for each set of linked bits, use is made of the syndrome, when it is not zero, for detecting the erroneous bits not invalidated by the error detecting codes.

14. A process according to claim 11, in which the information and redundancy words are transmitted in frames, wherein detection takes place of the validity of a received frame relative to its error detecting code and wherein for each set of linked frames definition takes place of a reduced matrix (H") constituted by the column vectors of the Hamming matrix (H) used on transmission and whereof the orders are equal to those of the linked frames invalidated by the error detecting codes and deduction takes place of another single matrix (H'"'"'^-1, H") for each set of linked frames, so that the product of this other matrix by a non-zero syndrome is equal to the error vector.

15. A process according to claim 14, wherein at least certain non-zero syndromes associated with sets of linked bits of linked frames are stored and wherein said non-zero syndromes are used for detecting erroneous frames not invalidated by the error detecting codes.