Our research is focused on mapping binary sequences to permutation sequences. It is established that an upper bound on the sum of the Hamming distance for all mappings exists, and this sum is used as a criterion to ascertain how good previously known mappings are. We further make use of permutation trellis codes to investigate the performance of certain permutation mappings in a power-line communications system, where background noise, narrow band noise and wide band noise are present. A new multilevel construction is presented next that maps binary sequences to permutation sequences, creating new mappings for which the sum of Hamming distances are greater than previous known mappings. It also proved that for certain lengths of sequences, the new construction can attain our new upper bound on the sum of Hamming distances. We further extend the multilevel construction by showing how it can be applied to other mappings, such as permutations with repeating symbols and mappings with nonbinary inputs. We also show that a subset of the new construction yields permutation sequences that are able to correct insertion and deletion errors as well. Finally, we show that long binary sequences, formed by concatenating the columns of binary permutation matrices, are subsets of the Levenshtein insertion/deletion correcting codes. / Prof. H. C. Ferreira

No description available.

A shared cryptographic key enables strong authentication. Candidate sources for creating such a shared key include biometrics and physically unclonable functions. However, these sources come with a substantial problem: noise in repeated readings. A fuzzy extractor produces a stable key from a noisy source. It consists of two stages. At enrollment time, the generate algorithm produces a key from an initial reading of the source. At authentication time, the reproduce algorithm takes a repeated but noisy reading of the source, yielding the same key when the two readings are close. For many sources of practical importance, traditional fuzzy extractors provide no meaningful security guarantee. This dissertation improves key derivation from noisy sources. These improvements stem from three observations about traditional fuzzy extractors. First, the only property of a source that standard fuzzy extractors use is the entropy in the original reading. We observe that additional structural information about the source can facilitate key derivation. Second, most fuzzy extractors work by first recovering the initial reading from the noisy reading (known as a secure sketch). This approach imposes harsh limitations on the length of the derived key. We observe that it is possible to produce a consistent key without recovering the original reading of the source. Third, traditional fuzzy extractors provide information-theoretic security. However, security against computationally bounded adversaries is sufficient. We observe fuzzy extractors providing computational security can overcome limitations of traditional approaches. The above observations are supported by negative results and constructions. As an example, we combine all three observations to construct a fuzzy extractor achieving properties that have eluded prior approaches. The construction remains secure even when the initial enrollment phase is repeated multiple times with noisy readings. Furthermore, for many practical sources, reliability demands that the tolerated noise is larger than the entropy of the original reading. The construction provides security for sources of this type by utilizing additional source structure, producing a consistent key without recovering the original reading, and providing computational security.

Today’s digital communication systems perform data transfers at the rate of millions of bits per minute, with data errors in the order of l/6th error per day. This magnitude of errorless communication is now possible because of sophisticated error correcting codes. Many types of error codes are employed today in three distinct areas of digital data communication: human to computer; data source to computer; computer to computer; and intra-computer; we are concerned here with intra-computer communication. This research is primarily a mathematical study of error codes in general to explore the possibilities of each major type for the purpose of implementation in real systems. The author was inspired toward this goal by several people and self-feelings. The first, was a definite affinity toward orderliness and the logical sequence of formal mathematics. Secondly, the thrusting of being assigned to a work project where computer maintenance and where all types of errors became important. And, finally an advisor who believes in “practical things”. The original portion of this endeavor is to be found in the conclusions drawn from each group of mathematical facts disclosed in the research. The particular bend of the author toward the cost/reliability/ efficiency of the system was not the intent of the theoretical mathematicians who did the majority of the work quoted herein. The author's contribution was to draw these ideas and works together and to form the conclusions based upon his experience and training as an Engineer. The primary conclusion is that multi-residue systematic codes appear to be the best choice for implementation of all around error correction and general hardware configurations. This conclusion is within the constraints that were laid down in the introduction of the research; 1) to not increase the cost of hardware, 2) to maintain or improve the system reliability, and 3) to maintain or increase the processing speed.

A Dissertation submitted in ful llment of the requirements for the degree of Master of Science in the School of Electrical and Information Engineering January, 2017 / Permutation codes provide the required redundancy for error correction in a noisy communication channel. Combined with MFSK modulation, the outcome produces an e cient system reliable in combating background and impulse noise in the com- munication channel. Part of this can be associated with how the redundancy scales up the amount of frequencies used in transmission. Permutation coding has also shown to be a good candidate for error correction in harsh channels such as the Powerline Communication channel. Extensive work has been done to construct permutation code books but existing decoding algorithms become impractical for large codebook sizes. This is because the algorithms need to compare the received codeword with all the codewords in the codebook used in encoding. This research therefore designs an e cient soft-decision decoder of Permutation codes. The decoder's decision mechanism does not require lookup comparison with all the codewords in the codebook. The code construction technique that derives the codebook is also irrelevant to the decoder. Results compare the decoding algorithm with Hard-decision plus Envelope Detec- tion in the Additive White Gaussian Noise (AWGN) and Rayleigh Fading Channels. The results show that with lesser iterations, improved error correction performance is achieved for high-rate codes. Lower rate codes require additional iterations for signi cant error correction performance. The decoder also requires much less comup- tational complexity compared with existing decoding algorithms. / MT2017

No description available.

No description available.

AX.25 packet radio is a popular means of data communications which has found many wide spread applications. For error control, AX.25 packet radio currently uses the go-back-N ARQ scheme which makes no attempt to correct errors, but only re-transmits packets which have been received with errors. This can lead to a very inefficient system when the channel error rate becomes substantially large. It has been found that by adding forward error correction (FEC) to the packet, the system performance can be substantially improved. This thesis studies the performance of various BCH codes, the (23,12) Golay code, Reed-Solomon codes, and different rate convolutional codes with varying constraint lengths when used in conjunction with the go-back-N ARQ. Code combining and concatenation are also studied. The performance of these codes is based on throughput performance, code rate, and system complexity. It is found that the (255,187) Reed-Solomon and the 1/2 rate v=9 convolutional codes can greatly enhance the performance of the AX.25 packet radio system. These codes provide good throughput performance over a large range of bit error rates and both are readily implemented. In conclusion, error control codes should be included with the AX.25 packet radio in order to improve its performance over noisy channels. / Master of Science

A transient fault in an array of processing elements results in an inconsistent or incorrect state in the processing element. If the erroneous information has already propagated before detection occurs, then the neighboring processing elements can also be in an incorrect state. Restarting the computation from the beginning every time a transient fault occurs is not only very inefficient but, in real-time computations, may not be possible. This thesis suggests the idea of "rollback" to recover from transient faults. Rollback is done by saving the state of the processing element at different instants of time. When an error is detected, backtracking is done to a consistent state and computation resumes from that state. The rollback algorithm is distributed in nature so that there is no single point of failure in the fault recovery mechanism. / Master of Science

Most existing fault tolerant systems employ some form of dynamic redundancy and can be considered to be incident driven. Their recovery mechanisms are triggered by the detection of a fault. This dissertation investigates an alternative approach to fault tolerant design where the redundant system restores itself periodically to correct errors before they build up to the point of system failure. It is shown that periodically self restoring systems can be designed to be tolerant of both transient (intermittent) and permanent hardware faults. Further, the reliability of such designs is not compromised by fault latency. The periodically self restoring redundant (PSRR) systems presented in this dissertation employ, in general, N computing units (CU's) operating redundantly in synchronization. The CU's communicate with each other periodically to restore units that may have failed due to transient faults. This restoration is initiated by an interrupt from an external (fault tolerant) clocking circuit. A reliability model for such systems is developed in terms of the number of CU's in the system, their failure rates and the frequency of system restoration. Both transient and permanent faults are considered. The model allows the estimation of system reliability and mean time to failure. A restoration algorithm for implementing the periodic restoration process in PSRR systems is also presented. Finally a design procedure is described that can be used for designing PSRR systems to meet desired reliability specifications. / Ph. D.