On the Structure of Real-Time Source Coders

On the Structure of Real-Time Source Coders By H. S. WITSENHAUSEN (Manuscript received January 30, 1979) The outputs of a discrete time source with memory are to be encoded ("quantized" or "compressed") into a sequence of discrete variables. From this latter sequence, a receiver must attempt to approximate some features of the source sequence. Operation is in real time, and the distortion measure does not tolerate delays. Such a situation has been investigated over infinite time spans by B. McMillan. In the present work, only finite time spans are considered. The main result is the following. If the source is Ath-order Markov, one may, without loss, assume that the encoder forms each output using only the last k source symbols and the present state of the receiver's memory. An example is constructed, which shows that the Markov property is essential. The case of delay is also considered. I. INTRODUCTION The outputs of a discrete time source with memory are to be encoded ("quantized" or "compressed") into a sequence of discrete variables. From this latter sequence, a receiver must attempt to approximate some features of the source sequence. Operation is in real time, and the distortion measure does not tolerate delays. Such a situation has been investigated over infinite time spans in Ref. 1. In the present work, only finite time spans are considered. The main result is the following. If the source is ^th-order Markov, one may, without loss, assume that the encoder forms each output using only the last k source symbols and the present state of the receiver's memory.