Information and Coding for Channels with Block Interference (Spread-Spectrum, Computer Memory).

Abstract

A class of channels called channels with block interference is defined and their capacities are determined. These channels are generalizations of channels considered by McEliece and Stark in that the states of a block interference channel are allowed to be dependent in a block but are independent of each other from block to block. The block interference channels are divided into two groups: block interference channels with side information and block interference channels without side information, depending on the presence or the absence of information concerning the current state of the channel at the decoder. It is shown that the capacity of a block interference channel without side information is less than but asymptotically approaches the capacity of the block interference channel with side information, as the block length increases. It is also shown that, if the decoder has full side information, then the capacity of a block interference channel is independent of the rate of side information provided to the encoder. We determine the capacity region of a channel with partial side information at the encoder and examine its asymptotic behavior. We give a few examples of block interference channels which include variable-state block interference channels and two-dimensional block interference channels and determine their capacities. Variable-state block interference channels have applications to frequency-hopped spread-spectrum systems which suffer from fading or jamming. We introduce a new test pattern technique for frequency-hopped spread-spectrum systems. Using the test pattern the decoder estimates which parts of the blocks are affected by interference. Two-dimensional block interference channels have applications to r and om access memories (RAMs) which suffer from row and column faults. We introduce a new coding scheme for codes on RAMs with row and column faults.