Variable Length error-correcting Codes and Reversible Variable Length Codes: Analysis and Applications

Abstract

A distinctive faculty with which humans are gifted is ‘communication’ – passing information from a source to a destination over a medium. The medium may technically be called ‘channel’. The long-standing issue is to achieve efficient and reliable communication over an unreliable channel. For efficient communication, we use ‘source codes’ which provide a compressed representation of the information. Reliability is obtained by using ‘channel codes’ which protect information from corruptions by adding structured redundancy into it. Communication is always over a channel and the channel, as mentioned above is invariably subjected to disturbances or noise. To minimize the effects of noise, coding is essential. Joint source channel coding (JSCC) is considered as the most promising scheme for communication over wireless channels, in view of its ability to cope with varying channel quantities. The direct source-channel mapping scheme is a good candidate for joint source channel coding. This thesis discusses two types of direct source channel mapped JSCC - Variable Length Error-correcting Codes (VLECs) and Reversible Variable Length Codes (RVLCs). The combinatorial results are important and these provide limitations on search of a code. We have derived an improved combinatorial bound on average codeword length of a subclass of VLECs. Further, we have considered constant length error correcting codes, available in literature, and developed an algorithm to generate VLECs which can be used in real-time applications. Code construction is incomplete without a decoding algorithm. To reduce the complexity of the decoding algorithm, we have developed a modified method of “Maximum Likelihood VLEC Decoding” which converts exponential search into a tabular search, and thereby reduces the computation time.