M.Ing. / In practical transmission or storage systems, the convolutional encoding and Viterbi decoding scheme is widely used to protect the data from substitution errors. Two independent insertion/deletion/substitution (IDS) error correcting designs, working on the convolutional encoder and the Viterbi decoder respectively, are shown in this thesis. The Levenshtein distance has previously been postulated to be a suitable branch comparison metric for the Viterbi algorithm on channels with not only substitution errors, but also insertion/deletion errors. However, to a large extent, this hypothesis has still to be investigated. In the first coding scheme, a modified Viterbi algorithm based on the Levenshtein distance metric is used as the decoding algorithm. Our experiments give evidence that the modified Viterbi algorithm with the Levenshtein distance metric is suitable as an applicable decoding algorithm for IDS channels. In the second coding scheme, a new type of convolutional code called the path-pruned convolutional code is introduced on the encoder side. By periodically deleting branches in a high rate convolutional code trellis diagram to create a specific insertion/deletion error correcting block codeword structure in the encoded sequence, we can obtain an encoding system to protect against insertion, deletion and substitution errors at the same time. Moreover, the path-pruned convolutional code is an ideal code to use for unequal error protection. Therefore, we also present an application of the rate-compatible path-pruned convolutional codes over IDS channels.

Wai-shing Lee. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 114). / Abstracts in English and Chinese. / Contents --- p.i / List of Figures --- p.iv / List of Tables --- p.v / Abstract --- p.vi / Acknowledgement --- p.vii / Chapter Chapter 1. --- Layout of the thesis --- p.1 / Chapter Chapter 2. --- Introduction --- p.3 / Chapter 2.1 --- What is the reasoning problem? --- p.3 / Chapter 2.2 --- Fundamental nature of Knowledge --- p.4 / Chapter 2.3 --- Fundamental methodology of Reasoning --- p.7 / Chapter 2.4 --- Our intended approach --- p.9 / Chapter Chapter 3. --- Probabilistic reasoning networks --- p.11 / Chapter 3.1 --- Overview --- p.11 / Chapter 3.2 --- Causality and influence diagrams --- p.11 / Chapter 3.3 --- Bayesian networks - influence diagrams endowed with a probability interpretation --- p.13 / Chapter 3.3.1 --- A detour to the interpretations of probability --- p.13 / Chapter 3.3.2 --- Bayesian networks --- p.15 / Chapter 3.3.3 --- Acyclicity and global probability --- p.17 / Chapter 3.4 --- Reasoning on probabilistic reasoning networks I - local updating formulae --- p.17 / Chapter 3.4.1 --- Rationale of the intended reasoning strategy --- p.18 / Chapter 3.4.2 --- Construction of the local updating formula --- p.19 / Chapter 3.5 --- Cluster graphs - another perspective to reasoning problems --- p.23 / Chapter 3.6 --- Semi-lattices - another representation of Cluster graphs --- p.26 / Chapter 3.6.1 --- Construction of semi-lattices --- p.26 / Chapter 3.7 --- Bayesian networks and semi-lattices --- p.28 / Chapter 3.7.1 --- Bayesian networks to acyclic semi-lattices --- p.29 / Chapter 3.8 --- Reasoning on (acyclic) probabilistic reasoning networks II - global updating schedules --- p.29 / Chapter 3.9 --- Conclusion --- p.30 / Chapter Chapter 4. --- Cyclic reasoning networks - a possibility? --- p.32 / Chapter 4.1 --- Overview --- p.32 / Chapter 4.2 --- A meaningful cyclic structure - derivation of the ideal gas law --- p.32 / Chapter 4.3 --- "What's ""wrong"" to be in a cyclic world" --- p.35 / Chapter 4.4 --- Communication - Dynamics - Complexity --- p.39 / Chapter 4.4.1 --- Communication as dynamics; dynamics to complexity --- p.42 / Chapter 4.5 --- Conclusion --- p.42 / Chapter Chapter 5. --- Cyclic reasoning networks ´ؤ error-control application --- p.43 / Chapter 5.1 --- Overview --- p.43 / Chapter 5.2 --- Communication schemes on cyclic reasoning networks directed to error-control applications --- p.43 / Chapter 5.2.1 --- Part I ´ؤ Local updating formulae --- p.44 / Chapter 5.2.2 --- Part II - Global updating schedules across the network --- p.46 / Chapter 5.3 --- Probabilistic reasoning based error-control schemes --- p.47 / Chapter 5.3.1 --- Local sub-universes and global universe underlying the error- control structure --- p.47 / Chapter 5.4 --- Error-control structure I --- p.48 / Chapter 5.4.1 --- Decoding algorithm - Communication between local sub- universes in compliance with the global topology --- p.51 / Chapter 5.4.2 --- Decoding rationales --- p.55 / Chapter 5.4.3 --- Computational results --- p.55 / Chapter 5.5 --- Error-control structure II --- p.57 / Chapter 5.5.1 --- Structure of the code and the corresponding decoding algorithm --- p.57 / Chapter 5.5.2 --- Computational results --- p.63 / Chapter 5.6 --- Error-control structure III --- p.66 / Chapter 5.6.1 --- Computational results --- p.70 / Chapter 5.7 --- Error-control structure IV --- p.71 / Chapter 5.7.1 --- Computational results --- p.73 / Chapter 5.8 --- Conclusion --- p.74 / Chapter Chapter 6. --- Dynamics on cyclic probabilistic reasoning networks --- p.75 / Chapter 6.1 --- Overview --- p.75 / Chapter 6.2 --- Decoding rationales --- p.76 / Chapter 6.3 --- Error-control structure I - exact solutions --- p.77 / Chapter 6.3.1 --- Dynamical invariant - a key to tackle many dynamical problems --- p.77 / Chapter 6.3.2 --- Dynamical invariant for error-control structure I --- p.78 / Chapter 6.3.3 --- Iteration dynamics --- p.79 / Chapter 6.3.4 --- Structure preserving property and the maximum a posteriori solutions --- p.86 / Chapter 6.4 --- Error-control structures III & IV - exact solutions --- p.92 / Chapter 6.4.1 --- Error-control structure III --- p.92 / Chapter 6.4.1.1 --- Dynamical invariants for error-control structure III --- p.92 / Chapter 6.4.1.2 --- Iteration dynamics --- p.93 / Chapter 6.4.2 --- Error-control structure IV --- p.96 / Chapter 6.4.3 --- Structure preserving property and the maximum a posteriori solutions --- p.98 / Chapter 6.5 --- Error-control structure II - exact solutions --- p.101 / Chapter 6.5.1 --- Iteration dynamics --- p.102 / Chapter 6.5.2 --- Structure preserving property and the maximum a posteriori solutions --- p.105 / Chapter 6.6 --- A comparison on the four error-control structures --- p.106 / Chapter 6.7 --- Conclusion --- p.108 / Chapter Chapter 7. --- Conclusion --- p.109 / Chapter 7.1 --- Our thesis --- p.109 / Chapter 7.2 --- Hind-sights and foresights --- p.110 / Chapter 7.3 --- Concluding remark --- p.111 / Appendix A. An alternative derivation of the local updating formula --- p.112 / Bibliography --- p.114

Thesis (Ph. D.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.

Thesis (Ph. D.)--Washington State University, December 2007. / Includes bibliographical references (p. 74-80).

<p>Wireless communication is always struggling with errors in the transmission. The digital data received from the radio channel is often erroneous due to thermal noise and fading. The error rate can be lowered by using higher transmission power or by using an effective error correcting code. Power consumption and limits for electromagnetic radiation are two of the main problems with handheld devices today and an efficient error correcting code will lower the transmission power and therefore also the power consumption of the device. </p><p>Duo-binary CTC is an improvement of the innovative turbo codes presented in 1996 by Berrou and Glavieux and is in use in many of today's standards for radio communication i.e. IEEE 802.16 (WiMAX) and DVB-RSC. This report describes the development of a duo-binary CTC decoder and the different problems that were encountered during the process. These problems include different design issues and algorithm choices during the design.</p><p>An implementation in VHDL has been written for Alteras Stratix II S90 FPGA and a reference-model has been made in Matlab. The model has been used to simulate bit error rates for different implementation alternatives and as bit-true reference for the hardware verification.</p><p>The final result is a duo-binary CTC decoder compatible with Alteras Stratix II designs and a reference model that can be used when simulating the decoder alone or the whole signal processing chain. Some of the features of the hardware are that block sizes, puncture rates and number of iterations are dynamically configured between each block Before synthesis it is possible to choose how many decoders that will work in parallel and how many bits the soft input will be represented in. The circuit has been run in 100 MHz in the lab and that gives a throughput around 50Mbit with four decoders working in parallel. This report describes the implementation, including its development, background and future possibilities.</p>

Exception handling is a programming language feature that can help increase the reliability of programs. However, not much work has been done on exception handling in visual programming languages. We present an approach for improving the exception handling mechanism in Forms/3, a declarative visual programming language based on the spreadsheet paradigm. We show how this approach can be added without sacrificing referential transparency and lazy evaluation in Forms/3. We then present a comparison of the Forms/3 exception handling mechanism with the mechanisms available in Java, C++, Prograph, Haskell and Microsoft Excel, based on their expressive powers. / Graduation date: 1998

Today's computer and network communication systems rely on authenticated and secure transmission of information, which requires computationally efficient and low bandwidth cryptographic algorithms. Among these cryptographic algorithms are the elliptic curve cryptosystems which use the arithmetic of finite fields. Furthermore, the fields of characteristic two are preferred since they provide carry-free arithmetic and at the same time a simple way to represent field elements on current processor architectures. Arithmetic in finite field is analogous to the arithmetic of integers. When performing the multiplication operation, the finite field arithmetic uses reduction modulo the generating polynomial. The generating polynomial is an irreducible polynomial over GF(2), and the degree of this polynomial determines the size of the field, thus the bit-lengths of the operands. The fundamental arithmetic operations in finite fields are addition, multiplication, and inversion operations. The sum of two field elements is computed very easily. However, multiplication operation requires considerably more effort compared to addition. On the other hand, the inversion of a field element requires much more computational effort in terms of time and space. Therefore, we are mainly interested in obtaining implementations of field multiplication and inversion. In this dissertation, we present several new bit-parallel hardware architectures with low space and time complexity. Furthermore, an analysis and refinement of the complexity of an existing hardware algorithm and a software method highly efficient and suitable for implementation on many 32-bit processor architectures are also described. / Graduation date: 1999

Graduation date: 1995

Balanced codes, in which each codeword contains equally many 1's and 0's, are useful in such applications as in optical transmission and optical recording. When balanced codes are used, the same number of 1's and 0's pass through the channel after the transmission of every word, so the channel is in a dc-null state. Optical channels require this property because they employ AC-coupled devices. Line codes, in which codewords may not be balanced, are also used as dc-free codes in such channels. In this thesis we present the research that leads to the following results: 1- Balanced codes These have higher information rate than existing codes yet maintain similar encoding and decoding complexities. 2- Error-correcting balanced codes In many cases, these give higher information rates and more efficient encoding and decoding algorithms than the best-known equivalent codes. 3- DC-Free coset codes A new technique to design dc-free coset codes was developed. These codes have better properties than existing ones. 4- Generalization of balanced codes -- Balanced codes are generalized in three ways among which the first is the most significant: a) Balanced codes with low dc level These codes are designed based on the combined techniques used in (1) and (3) above. A lower dc-level and higher transitions density is achieved at the cost of one extra check bit. These codes are much more attractive, to optical transmission, than the bare-bone balanced codes. b) Non-Binary Balanced Codes Balanced codes over a non-binary alphabet. c) Semi-Balanced Codes -- Codes in which the number of 1's and 0's in every code word differs by at most a certain value. 5- t-EC/AUED coset codes These are t error correcting/all unidirectional error detecting codes. Again the technique in (3) above is used to design t-EC/AUED coset codes. These codes obtain higher information rate than the best-known equivalent codes and yet maintain the same encoding/decoding complexity. / Graduation date: 1990

Wireless communication is always struggling with errors in the transmission. The digital data received from the radio channel is often erroneous due to thermal noise and fading. The error rate can be lowered by using higher transmission power or by using an effective error correcting code. Power consumption and limits for electromagnetic radiation are two of the main problems with handheld devices today and an efficient error correcting code will lower the transmission power and therefore also the power consumption of the device. Duo-binary CTC is an improvement of the innovative turbo codes presented in 1996 by Berrou and Glavieux and is in use in many of today's standards for radio communication i.e. IEEE 802.16 (WiMAX) and DVB-RSC. This report describes the development of a duo-binary CTC decoder and the different problems that were encountered during the process. These problems include different design issues and algorithm choices during the design. An implementation in VHDL has been written for Alteras Stratix II S90 FPGA and a reference-model has been made in Matlab. The model has been used to simulate bit error rates for different implementation alternatives and as bit-true reference for the hardware verification. The final result is a duo-binary CTC decoder compatible with Alteras Stratix II designs and a reference model that can be used when simulating the decoder alone or the whole signal processing chain. Some of the features of the hardware are that block sizes, puncture rates and number of iterations are dynamically configured between each block Before synthesis it is possible to choose how many decoders that will work in parallel and how many bits the soft input will be represented in. The circuit has been run in 100 MHz in the lab and that gives a throughput around 50Mbit with four decoders working in parallel. This report describes the implementation, including its development, background and future possibilities.