The Equivocation of Codes

Abstract

EQUIVOCATION was introduced by Shannon in the late 1940’s in seminal papers that kick-started the whole field of information theory. Much ground has been covered on equivocation’s counterpart, channel capacity and in particular, its bounds. However, less work has been carried out on the evaluation of the equivocation of a code transmitted across a channel.

The aim of the work covered in this thesis was to use a probabilistic approach to investigate and compare the equivocation of various codes across a range of channels. The probability and entropy of each output, given each input, can be used to calculate the equivocation. This gives a measure of the ambiguity and secrecy of a code when transmitted across a channel. The calculations increase exponentially in magnitude as both the message length and code length increase. In addition, the impact of factors such as erasures and deletions also serve to significantly complicate the process.

In order to improve the calculation times offered by a conventional, linearly-programmed approach, an alternative strategy involving parallel processing with a CUDA-enabled (Compute Unified Device Architecture) graphical processor was employed. This enabled results to be obtained for codes of greater length than was possible with linear programming. However, the practical implementation of a CUDA driven, parallel processed solution gave rise to significant issues with both the software implementation and subsequent platform stability.

By normalising equivocation results, it was possible to compare different codes under different conditions, making it possible to identify and select codes that gave a marked difference in the equivocation encountered by a legitimate receiver and an eavesdropper.

The introduction of code expansion provided a novel method for enhancing equivocation differences still further. The work on parallel processing to calculate equivocation and the use of code expansion was published in the following conference: Schofield, M., Ahmed, M. & Tomlinson, M. (2015), Using parallel processing to calculate and improve equivocation, in ’IEEE Conference Publications - IEEE 16th International Conference on Communication Technology’.

In addition to the novel use of a CUDA-enabled graphics process to calculated equivocation, equivocation calculations were also performed for expanded versions of the codes. Code expansion was shown to yield a dramatic increase in the achievable equivocation levels.

Once methods had been developed with the Binary Symmetric Channel (BSC), they were extended to include work with intentional erasures on the BSC, intentional deletions on the BSC and work on the Binary Erasure Channel (BEC). The work on equivocation on the BSC with intentional erasures was published in: Schofield, M. et al, (2016), Intentional erasures and equivocation on the binary symmetric channel, in ’IEEE Conference Publications - International Computer Symposium’, IEEE, pp 233-235.

The work on the BEC produced a novel outcome due to the erasure correction process employed. As the probability of an erasure occurring increases, the set of likely decoded outcomes diminishes. This directly impacts the output entropy of the system by decreasing it, thereby also affecting the equivocation value of the system. This aspect was something that had not been encountered previously.

The work also extended to the consideration of intentional deletions on the BSC and the Binary Deletion Channel (BDC) itself. Although the methods used struggled to cope with the additional complexity brought by deletions, the use of Varshamov-Tenengolts codes on the BSC with intentional deletions showed that family of codes to be well suited to the channel arrangement as well as having the capability to be extended to enable the correction of multiple deletions.