Joint source-channel coding with feedback

Communications is about conveying information from one point to another subject to certain performance constraints. The information is assumed to be generated by a source and may, for example, represent a voice waveform, the reading of a thermal sensor, or packets generated by a node in a network. The channel is the physical medium over which the actual transmission takes place. It might represent a telephone line, a fibre optic link or the air over which our voice propagates during a conversation. The channel is usually subject to disturbances of diverse nature, which for example in the case of a telephone link, might be cross talk from other users, frequency selective distortion or thermal noise. There are various approaches to this problem of conveying the source across the channel, the most common one being the separation based approach. In this approach, the problem of conveying the information is broken down into two parts: efficient representation (also called source coding) and reliable transmission (also called channel coding). Shannon showed that for a wide variety of situations, the breaking up of the original problem into these two simpler problems does not impose any restrictions on the performance of a communication system. However, this property may fail to hold in point-to-point communications if the source is non-ergodic, the channel is time-varying, the system is delay or complexity constrained, or when we are dealing with a network scenario. In this case, there are potential benefits to be gained by looking at the problem from a joint source-channel coding perspective rather than the two narrower perspectives of source and channel coding. Another result, again due to Shannon, shows that the presence of a noiseless feedback link from the output of the channel to the encoder does not increase the capacity of point-to-point memoryless channels. However the presence of a feedback link can help in decreasing the complexity of implementation as well as the delay associated with the system. In this thesis, we combine these two ideas to look at the problem of feedback communications from a joint source-channel coding perspective. We first outline a joint source-channel coding scheme and show rigorously that the expected number of channel uses to decode each source symbols approaches the source entropy divided by the channel capacity. This is a block decoding strategy and the complexity of this scheme is exponential in the block length. However, the system is optimal in the sense that no other scheme can decode source symbols with a lower number of channel uses on the average. We next focus on a modified low-complexity variant of the scheme considered earlier. This low-complexity implementation has a number of desirable properties. First, the source symbols are decoded one by one. The delay per source symbol is essentially a constant. Secondly, simulation results show that the symbol errors are confined locally and do not propagate. Thirdly, the scheme can adaptively learn the parameters of interest and approach optimal performance. Finally, the presence of a high capacity feedback link makes the structure of the encoder extremely simple. In the final part of the thesis, we extend the scheme that we have developed for the single-user scenario to the case when two users want to send data to the same receiver. We show that the computational complexity of each of the users remains the same as the single-user case, but the space complexity of one of the users increases. However, the reduction in complexity over the feedback-free case is still significant.