Some aspects of the construction and implementation of error-correcting linear codes
- Authors: Booth, Geoffrey L
- Date: 1978
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:20967 , http://hdl.handle.net/10962/5718
- Description: From Conclusion: The study of error-correcting codes is now approximately 25 years old. The first known publication on the subject was in 1949 by M. Golay, who later did much research into the subject of perfect codes. It has been recently established that all the perfect codes are known. R.W. Hamming presented his perfect single-error correcting codes in 1950, in ~n article in the Bell System Technical Journal. These codes turned out to be a special case of the powerful Bose-Chaudhuri codes which were discovered around 1960. Various work has been done on the theory of minimal redundancy of codes for a given error-correcting performance, by Plotkin, Gilbert, Varshamov and others, between 1950 and 1960. The binary BCH codes were found to be so close to the theoretical bounds that, to date, no better codes have been discovered. Although the BCH codes are extremely efficient in terms of ratio of information to check digits, they are not easily, decoded with a minimal amount of apparatus. Petersen in 1961 described an algorithm for d e coding BCH codes, but this was cumbersome compared with the majority-logic methods of Massey and others. Thus the search began for codes which are easily decoded with comparatively simple apparatus. The finite geometry codes which were described by Rudolph in a 1964 thesis were examples of codes which are easily decoded 58 by a small number of steps of majority logic. The simplicial codes of Saltzer are even better in this respect, since they can be decoded by a single step of majority logic, but are rather inefficient . The applications of coding theory have changed over the years, as well. The first computers were huge circuits of relays, which were unreliable and prone to errors. Error correcting codes were required to minimise the possibility of incorrect results. As vacuum tubes and later transistorised circuits made computers more reliable, the need for sophisticated and powerful codes in the computer world diminished. Other used presented themselves however, for example the control systems of unmanned space craft. Because of the difficulty of sending and receiving messages in this case, · very powerful codes were required. Other uses were found in transmission lines and telephone exchanges. The codes considered in this dissertation have, for the most part, been block codes for use on the binary symmetric channel. There are, however, several other applications, such as codes for use on an erasure channel, where bits are corrupted so as to be unrecognizable, rather than changed. There are also codes for burst-error correction, where chennel noise is not randomly distributed, but occurs in "bursts" a few bits long. Certain cyclic codes are of application in these cases. The theory of error correcting codes has risen from virtual non-existence in 1950 to a major and sophisticated part of communication theory. Judging from the articles in journals, it promises to be the subject of a great deal of research for some years to come.
- Full Text:
- Date Issued: 1978
- Authors: Booth, Geoffrey L
- Date: 1978
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:20967 , http://hdl.handle.net/10962/5718
- Description: From Conclusion: The study of error-correcting codes is now approximately 25 years old. The first known publication on the subject was in 1949 by M. Golay, who later did much research into the subject of perfect codes. It has been recently established that all the perfect codes are known. R.W. Hamming presented his perfect single-error correcting codes in 1950, in ~n article in the Bell System Technical Journal. These codes turned out to be a special case of the powerful Bose-Chaudhuri codes which were discovered around 1960. Various work has been done on the theory of minimal redundancy of codes for a given error-correcting performance, by Plotkin, Gilbert, Varshamov and others, between 1950 and 1960. The binary BCH codes were found to be so close to the theoretical bounds that, to date, no better codes have been discovered. Although the BCH codes are extremely efficient in terms of ratio of information to check digits, they are not easily, decoded with a minimal amount of apparatus. Petersen in 1961 described an algorithm for d e coding BCH codes, but this was cumbersome compared with the majority-logic methods of Massey and others. Thus the search began for codes which are easily decoded with comparatively simple apparatus. The finite geometry codes which were described by Rudolph in a 1964 thesis were examples of codes which are easily decoded 58 by a small number of steps of majority logic. The simplicial codes of Saltzer are even better in this respect, since they can be decoded by a single step of majority logic, but are rather inefficient . The applications of coding theory have changed over the years, as well. The first computers were huge circuits of relays, which were unreliable and prone to errors. Error correcting codes were required to minimise the possibility of incorrect results. As vacuum tubes and later transistorised circuits made computers more reliable, the need for sophisticated and powerful codes in the computer world diminished. Other used presented themselves however, for example the control systems of unmanned space craft. Because of the difficulty of sending and receiving messages in this case, · very powerful codes were required. Other uses were found in transmission lines and telephone exchanges. The codes considered in this dissertation have, for the most part, been block codes for use on the binary symmetric channel. There are, however, several other applications, such as codes for use on an erasure channel, where bits are corrupted so as to be unrecognizable, rather than changed. There are also codes for burst-error correction, where chennel noise is not randomly distributed, but occurs in "bursts" a few bits long. Certain cyclic codes are of application in these cases. The theory of error correcting codes has risen from virtual non-existence in 1950 to a major and sophisticated part of communication theory. Judging from the articles in journals, it promises to be the subject of a great deal of research for some years to come.
- Full Text:
- Date Issued: 1978
Some aspects of the theory, application, and computation of generalised inverses of matrices
- Authors: Cretchley, Partricia C
- Date: 1977
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: http://hdl.handle.net/10962/6212 , vital:21063
- Description: The idea of generalising the classical notion of the inverse of a non-singular matrix arose as far back as in 1920, but it was not until the late fifties that the development of the theory gained any impetus. Since then , as is the case in the development of many new concepts , work done in parallel in various parts of the world has resulted in a great deal of untidiness in the literature : confusion over terminology , and even duplication of theory. More recently, however, some attempts have been made to bring together people active in the field of generalised inverses, in order to reach consensus on some aspects of definition and terminology, and to publish more general works on the subject. Towards this purpose, a symposium on the theory and application of generalised inverses of matrices was held in Lubbock, Texas, and its proceedings published in 1968 (see [25] ). A few other works of this nature (see [4], (19a] ) have appeared , but the bulk of the literature still comprises numerous diverse papers offering further ideas on the theoretical properties which these matrices have , and drawing attention to their application in areas of statistics , numerical analysis , filtering , modern control and estimation theory, pattern recognition and many others. This essay offers a look at generalised inverses in the following way: firstly a broad basis and background is established in the first three chapters to provide greater understanding of the motivation for the remaining chapters, where the approach then changes to become far more detailed. Within this general framework, Chapter 1 offers a brief glimpse of the history and development of work in the field. In Chapter 2 some of the most significant properties of these inverses are described, while in Chapters 3 and 4 and 5 attention is given to interesting and remarkable computational algorithms relating to generalised inverses (some well suited to machine processing). The material of Chapters 4 and 5 is largely due to Decell, Stallings and Boullion, and Tanabe, in [6], [24] and [27], respectively, while the source of material for the first three chapters is the literature generally, with Penrose's two papers providing a rough framework for Chapters 1 and 2 (see [17]).
- Full Text:
- Date Issued: 1977
- Authors: Cretchley, Partricia C
- Date: 1977
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: http://hdl.handle.net/10962/6212 , vital:21063
- Description: The idea of generalising the classical notion of the inverse of a non-singular matrix arose as far back as in 1920, but it was not until the late fifties that the development of the theory gained any impetus. Since then , as is the case in the development of many new concepts , work done in parallel in various parts of the world has resulted in a great deal of untidiness in the literature : confusion over terminology , and even duplication of theory. More recently, however, some attempts have been made to bring together people active in the field of generalised inverses, in order to reach consensus on some aspects of definition and terminology, and to publish more general works on the subject. Towards this purpose, a symposium on the theory and application of generalised inverses of matrices was held in Lubbock, Texas, and its proceedings published in 1968 (see [25] ). A few other works of this nature (see [4], (19a] ) have appeared , but the bulk of the literature still comprises numerous diverse papers offering further ideas on the theoretical properties which these matrices have , and drawing attention to their application in areas of statistics , numerical analysis , filtering , modern control and estimation theory, pattern recognition and many others. This essay offers a look at generalised inverses in the following way: firstly a broad basis and background is established in the first three chapters to provide greater understanding of the motivation for the remaining chapters, where the approach then changes to become far more detailed. Within this general framework, Chapter 1 offers a brief glimpse of the history and development of work in the field. In Chapter 2 some of the most significant properties of these inverses are described, while in Chapters 3 and 4 and 5 attention is given to interesting and remarkable computational algorithms relating to generalised inverses (some well suited to machine processing). The material of Chapters 4 and 5 is largely due to Decell, Stallings and Boullion, and Tanabe, in [6], [24] and [27], respectively, while the source of material for the first three chapters is the literature generally, with Penrose's two papers providing a rough framework for Chapters 1 and 2 (see [17]).
- Full Text:
- Date Issued: 1977
Remarks on formalized arithmetic and subsystems thereof
- Brink, C
- Authors: Brink, C
- Date: 1975
- Subjects: Gödel, Kurt , Logic, Symbolic and mathematical , Semantics (Philosophy) , Arithmetic -- Foundations , Number theory
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:5424 , http://hdl.handle.net/10962/d1009752 , Gödel, Kurt , Logic, Symbolic and mathematical , Semantics (Philosophy) , Arithmetic -- Foundations , Number theory
- Description: In a famous paper of 1931, Gödel proved that any formalization of elementary Arithmetic is incomplete, in the sense that it contains statements which are neither provable nor disprovable. Some two years before this, Presburger proved that a mutilated system of Arithmetic, employing only addition but not multiplication, is complete. This essay is partly an exposition of a system such as Presburger's, and partly an attempt to gain insight into the source of the incompleteness of Arithmetic, by linking Presburger's result with Gödel's.
- Full Text:
- Date Issued: 1975
- Authors: Brink, C
- Date: 1975
- Subjects: Gödel, Kurt , Logic, Symbolic and mathematical , Semantics (Philosophy) , Arithmetic -- Foundations , Number theory
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:5424 , http://hdl.handle.net/10962/d1009752 , Gödel, Kurt , Logic, Symbolic and mathematical , Semantics (Philosophy) , Arithmetic -- Foundations , Number theory
- Description: In a famous paper of 1931, Gödel proved that any formalization of elementary Arithmetic is incomplete, in the sense that it contains statements which are neither provable nor disprovable. Some two years before this, Presburger proved that a mutilated system of Arithmetic, employing only addition but not multiplication, is complete. This essay is partly an exposition of a system such as Presburger's, and partly an attempt to gain insight into the source of the incompleteness of Arithmetic, by linking Presburger's result with Gödel's.
- Full Text:
- Date Issued: 1975
- «
- ‹
- 1
- ›
- »