A model in which a transmitterTsends a message to a receiverRvia shared random-access memory is analyzed. In the model, the random-access memory consists ofLindividually addressable cells, each of which may be set to a value from a finite alphabet. A messagemis sent by writing values into some of the memory cells so that the memory state is consistent with some codeword form. The model differs from traditional source coding in several respects. The codeword may specify values for a noncontiguous subset of the memory cells and allow the remaining unspecified cells to be filled in by other users as they wish. Also, the transmitterTmay attempt to avoid writing a full codeword into memory by first reading some cells to determine the initial memory state partially. Thus, the cells accessed for transmission and the cells specified by a codeword may be distinct, unlike traditional noiseless source coding where the symbols sent and symbols received are identical. Here we analyze the operational characteristics of the transmitterT. It is shown that the number of accesses byTobeys a generalized Kraft inequality. Lower bounds are given for the worst case and average number of accesses.

Four costs of a retrieval algorithm are the number of bits needed to store a representation of a data base, the number of those bits which must be accessed to answer a retrieval question, the number of bits of state information required, and the logic complexity of the algorithm.Firm lower bounds are given to measures of the first three costs for simple binary retrieval problems.Systems are constructed which attain each bound separately.A system which finds the value of the kth bit in an N-bit string attains all bounds simultaneously.For two other more complex retrieval problems there are trading curves between storage and worst-case access, and between storage and average access.Lower and upper bounds to the trading curves are found.Minimal storage is a point of discontinuity on both curves, and for some complex problems large increases in storage are needed to approach minimal access.The cost of a complete updating algorithm is taken to be the number of bits it reads and/or writes in updating the representation of a data base.Lower bounds to measures of this cost are cited.Optimal minimal-storage systems also have minimal update cost.Optimal minimal-access systems with large storage cost also have large update cost, but a small increase in storage for such a system may reduce update cost dramatically.

The hypothesis-testing problem has recently been studied under a finite-memory constraint. However, most work has been concerned with the large-sample theory. Here we study the small-sample theory for binary-valued observations.