Already Gallager provided two of such algorithms whose decoding complexity per iteration is linear in the block length. This sparsity property is the bedrock of efficient decoding algorithms. LDPC codes, as originally proposed, are binary linear codes with a very sparse parity-check matrix. This groundbreaking result came-with the help of a computer-after a series of papers analyzed the binary linear code coming from a putative projective plane of order 10.Ī very important class of codes which was sensibly influenced by geometric constructions is given by low-density parity-check (LDPC) codes, which were introduced by Gallager in his seminal 1962 paper. The most striking example is certainly the non-existence proof of a finite projective plane of order 10 shown in. The relations between these two research areas had also a strong impact in the opposite direction. Generalizations of these constructions have been studied since the 70’s and are still the subject of active research (see ). Their idea was to use the incidence matrix of the plane as a generator matrix or as a parity-check matrix of a linear code, showing that the underlying geometry can be translated in metric properties of the corresponding codes. The close interplay between coding theory and finite geometry has emerged multiple times in the last 60 years, starting from the works of Prange and Rudolph, where they proposed to construct linear codes starting from projective planes.
0 Comments
Leave a Reply. |