Block coding for the binary symmetric broadcast channel with two receivers is investigated. A graph-theoretic approach to the construction of a class of block codes with unequal error protection for two different sets of messages is presented. A code in this class is a direct sum of two component codes; each set of messages is encoded based on one component code. The codes in this class are easy to implement. Decoding of these codes is presented, and lower bounds on the achievable rates of these codes are derived. The bounds are tighter than the Katsman's bounds.

We relate coding for the two-user multiple-access binary adder channel to a problem in graph theory, known as the independent set problem. Graph-theoretic approaches to coding for both synchronized and nonsynchronized two-user adder channels are presented. Using the Tuŕan theorem on the independence number of a simple graph, we are able to improve the lower bounds on the achievable rates of uniquely and\delta-decodable codes for the synchronized adder channel derived by Kasami and Lin. We are also able to derive lower bounds on the achievable rates of uniquely decodable codes for the nonsynchronized adder channel. We show that the rates of Deaett-Wolf codes for the nonsynchronized adder channel fall below the bounds. Synchronizing sequences for the nonsynchronized adder channel are constructed.

A scheme for storing information in a memory system with defective memory ceils using "additive" codes was proposed by Kuznetsov and Tsybakov. When a source message is to be stored in a memory with defective cells, a code vectorxmasking the defect pattern of the memory is formed by adding a vector defined by the message and the defect pattern to the encoded message, and thenxis stored. The decoding process does not require the defect information. Considerably better bounds on the information rate of codes of this type which are capable of masking multiple defects and correcting multiple temporary errors are presented. The difference between the upper and lower bounds approaches the difference between the known best upper and lower bounds for random error correcting linear codes as the word length becomes large. Examples of efficient codes for masking double or fewer defects and correcting multiple temporary errors are presented.