Design of proximity detecting codes

Abstract

Information can be transmitted over a channel synchronously or asynchronously. When the communication channel is asynchronous, then the receiver is not sure when the data transmitted by the sender will be received. To make the asynchronous channel delay insensitive, codes like unordered codes have been proposed. Although these codes are delay insensitive, the receiver still has to wait for all the 1s in the transmitted data to be received before sending an acknowledge signal to the sender. A new class of codes called Proximity Detecting Codes can be used to overcome this problem associated with asynchronous channels. A t-proximity detecting (t-PD) code can detect when a received word is within distance t from the transmitted codeword, when using a four-phase asynchronous communication protocol (or other similar protocols). A non-trivial t-proximity detecting code must be unordered. However, not all unordered codes are t-proximity detecting. This thesis analyzes the designs and bounds for systematic proximity detecting codes.