Search NASA⌕ Search

Engineering topics

Gallager, R. G.

Publications and source records attributed to Gallager, R. G..

13 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1976

Basic limits on protocol information in data communications networks

The paper considers basic limitations on the amount of protocol information that must be transmitted in a data communication network to keep track of source and receiver addresses and of the starting and stopping of messages. Assuming Poisson message arrivals between each communicating source-receiver pair, a lower bound is found on the required protocol information for message. This lower bound is the sum of two terms, one for the message-length information, which depends only on the distribution of message lengths, and the other for the message-start information, which depends only on the product of the source-receiver pair arrival rate and the expected delay for transmitting the message. Two strategies are developed which, in the limit of large numbers of sources and receivers, almost meet the lower bound on protocol information.

Gallager, R. G.↗
NASA NTRS1975

Optimal source codes for geometrically distributed integer alphabets

An approach is shown for using the Huffman algorithm indirectly to prove the optimality of a code for an infinite alphabet if an estimate concerning the nature of the code can be made. Attention is given to nonnegative integers with a geometric probability assignment. The particular distribution considered arises in run-length coding and in encoding protocol information in data networks. Questions of redundancy of the optimal code are also investigated.

Gallager, R. G.↗
NASA NTRS1974

Tree encoding for symmetric sources with a distortion measure

A simple algorithm is developed for mapping the outputs of a source into a set of code sequences generated by a tree code. The algorithm is analyzed for the case of a source producing discrete independent equiprobable letters when the distortion measure satisfies a certain symmetry condition. It is shown that the algorithm is capable of achieving an average distortion as close as desired to the minimum average distortion for the code rate given by Shannon's rate-distortion theorem.

Gallager, R. G.↗
NASA NTRS1973

The random coding bound is tight for the average code.

The random coding bound of information theory provides a well-known upper bound to the probability of decoding error for the best code of a given rate and block length. The bound is constructed by upperbounding the average error probability over an ensemble of codes. The bound is known to give the correct exponential dependence of error probability on block length for transmission rates above the critical rate, but it gives an incorrect exponential dependence at rates below a second lower critical rate. Here we derive an asymptotic expression for the average error probability over the ensemble of codes used in the random coding bound. The result shows that the weakness of the random coding bound at rates below the second critical rate is due not to upperbounding the ensemble average, but rather to the fact that the best codes are much better than the average at low rates.

Gallager, R. G.↗