Algebraic and Combinatorial Methods for Error-Correcting Codes with Applications to Fault-Tolerant Logic
Astola, Helena (2015)
Astola, Helena
Tampere University of Technology
2015
Teknis-taloudellinen tiedekunta - Faculty of Business and Technology Management
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Julkaisun pysyvä osoite on
https://urn.fi/URN:ISBN:978-952-15-3626-7
https://urn.fi/URN:ISBN:978-952-15-3626-7
Tiivistelmä
In this thesis, algebraic and combinatorial tools are used in the study and applications of error-correcting codes and logic design. In the first part, decision diagrams and error-correcting codes are combined to introduce fault-tolerance to logic circuits. The proposed method introduces fault-tolerance to the representations of functions, and hence, no additional checker circuitry is needed in the implementations. With suitable technology, the layout and complexity of the final design is directly determined by the error-correcting decision diagram. The fault-tolerance analysis shows that, even with moderately high gate error probabilities, such robust constructions will have a significantly decreased probability of an incorrect output. In terms of complexity, using codes in the Lee metric reduces the number of nodes of the resulting diagram compared to using codes in the Hamming metric.
The second part of this thesis focuses on finding the largest code with a given minimum distance, which is an important problem in coding theory. The main result in this part is the sharpening of the linear programming bound of linear Lee codes, which is based on an invariance-type property of the Lee-compositions of a linear code. Based on this property, additional constraints can be introduced to the linear programming problem. The results show improvements to the bounds with several parameter values when compared to the general linear programming bound. Some other properties of the Lee-compositions of a linear code are studied, leading to a faster and more accurate execution of the linear programming problem. In addition, the sharpening of the linear programming bound is introduced for codes in the Euclidean distance.
The second part of this thesis focuses on finding the largest code with a given minimum distance, which is an important problem in coding theory. The main result in this part is the sharpening of the linear programming bound of linear Lee codes, which is based on an invariance-type property of the Lee-compositions of a linear code. Based on this property, additional constraints can be introduced to the linear programming problem. The results show improvements to the bounds with several parameter values when compared to the general linear programming bound. Some other properties of the Lee-compositions of a linear code are studied, leading to a faster and more accurate execution of the linear programming problem. In addition, the sharpening of the linear programming bound is introduced for codes in the Euclidean distance.
Kokoelmat
- Väitöskirjat [4888]