Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
Search Results
Item Detection of Binary Sources Over Discrete Channels with Additive Markov Noise(1994) Alajaji, Fady; Phamdo, N.; Farvardin, Nariman; Fuja, Tom E.; ISRWe consider the problem of directly transmitting a binary source with an inherent redundancy over a binary channel with additive stationary ergodic Markov noise. Out objective is to design an optimum receiver which fully utilizes the source redundancy in order to combat the channel noise.We investigate the problem of detecting a binary iid non-uniform source transmitted across the Markov channel. Two maximum a posteriori (MAP) formulations are considered: a sequence MAP detection and an instantaneous MAP detection. The two MAP detection problems are implemented using a modified version of the Viterbi decoding algorithm and a recursive algorithm. Necessary and sufficient conditions under which the sequence MAP detector becomes useless as well as simulation results are presented. A comparison between the performance of the proposed system with that of a (substantially more complex) traditional tandem source-channel coding scheme exhibits a better performance for the proposed scheme at relatively high channel bit error rates.
The same detection problem is then analyzed for the case of a binary symmetric Markov source. Analytical and simulation results show the existence of a "mismatch" between the source and the channel. This mismatch is reduced by the use of a rate-one convolutional encoder. Finally, the detection problem is generalized for the case of a binary non-symmetric Markov source.
Item A Communication Channel Modeled on Contagion(1993) Alajaji, Fady; Fuja, Tom E.; ISRWe introduce a binary additive communication channel with memory. The noise process of the channel is generated according to the contagion model of George Polya; our motivation is the empirical observation of Stapper et. al. that defects in semiconductor memories are well described by distributions derived from Polya's urn scheme. The resulting channel is stationary but not ergodic, and it has many interesting properties.We First derive a maximum likelihood (ML) decoding algorithm for the channel; it turns out that ML decoding is equivalent to decoding a received vector onto either the closest codeword or the codeword that is farthest away, depending on whether an ﲡpparent epidemic has occurred. We next show that the Poly-contagion channel is an ﲡveraged channel in the sense of Ahlswede (and others) and that its capacity is zero. We then demonstrate that the Poly- contagion channel is a counter-example to the adage, ﲭemory cannot decrease capacity ; the capacity of the Poly-contagion channel is actually less than that of the associated memoryless channel. Finally, we consider a finite-memory version of the Poly-contagion model; this channel is (unlike the original) ergodic with a non-zero capacity that increases with increasing memory.
Item Optical Orthogonal Codes with Unequal Auto- and Cross- Correlation Constraints(1992) Yang, G-C.; Fuja, Tom E.; ISRAn optical orthogonal code (OOC)is collection of binary sequences with good auto-and cross-correlation properties; they were defined by Salehi and others as a means of obtaining code division multiple access on optical networks. Up to now all work on OOC's have assumed that the constraint placed on the auto- correlation and that placed on the cross-correlation are the same. In this paper we consider codes for which the two constraints are not equal. Specifically, we develop bounds on the size of such OOC's and demonstrate construction techniques for building them. The results demonstrate that a significant increase in the code size is possible by letting the auto- correlation constraint exceed the cross-correlation constraint. These results suggest that for a given performance requirement the optimal OOC may be one with unequal constraints.This paper also views OOC's with unequal auto- and cross-correlation constraints as constant-weight unequal error protection (UEP) codes with two levels of protection. The bounds derived are interpreted from this viewpoint and are compared with previous work on UEP codes.
Item A Generalized Gilbert-Varshamov Bound Derived via Analysis of a Code-Search Algorithm(1992) Gu, Junfeng; Fuja, Tom E.; ISRThis correspondence derives a generalization of the Gilbert- Varshamov bound that is applicable to block codes whose codewords must be drawn from irregular sets; the bound improves by a factor of four a similar result recently published by Kolesnik and Krachkovsky. It is derived by analyzing a code search algorithm we refer to as the "Altruistic Algorithm". This algorithm iteratively deletes potential codewords so that at each iteration the "worst" candidate is removed; the bound is derived by demonstrating that, as the algorithm proceeds, the average volume of a sphere of a given radius approaches the maximum such volume and so a bound previously expressed in terms of the maximum volume can in fact be expressed in terms of the average volume. Examples of applications where the bound is relevant include error-correcting (d, k)- constrained codes and binary codes for code division multiple access.Item Distributed Decoding of Cyclic Block Codes Using a Generalization of Majority-Logic Decoding(1992) Murad, A.H.; Fuja, Tom E.; ISROne-step majority-logic decoding is one of the simplest algorithms for decoding cyclic block codes. However, it is an effective decoding scheme for very few codes. This paper presents a generalization based on the "common-symbol decoding problem." Suppose one is given M (possibly different) codes over the same field; suppose further that the codewords share a single symbol in common. The common-symbol decoding problem is that of estimating the symbol in the common position. (This is equivalent to one-step majority logic decoding when each of the "constituent" codes is a simple parity check.) This paper formulates conditions under which this decoding is possible and presents a simple algorithm that accomplishes the same. When applied to decoding cyclic block codes, this technique yields a decoder structure ideal for parallel implementation. Furthermore, this approach frequently results in a decoder capable of correcting more errors than one-step majority-logic decoding. To demonstrate the simplicity of the resulting decoders, an example is presented.Item The Performance of Focused Error Control Codes(1990) Alajaji, Fady; Fuja, Tom E.; ISRConsider an additive noise channel with inputs and outputs in the field GF (q ) where q > 2; every time a symbol is transmitted over such a channel, there are q - 1 different errors that can occur, corresponding to the q - 1 non-zero elements that the channel can add to the transmitted symbol. In many data communication/ storage systems, there are some errors that occur much more frequently than others; however, traditional error correcting codes- designed with respect to the Hamming metric - treat each of these q - 1 errors the same. Fuja and Heegard have designed a class of codes, called focused error control codes, that offer different levels of protection against "common" and "uncommon" errors; the idea is to define the level of protection in a way based not only on the number of errors, but the kind as well. In this paper, the performance of these codes is analyzed with respect to idealized "skewed" channels as well as realistic non-binary modulation schemes. It is shown that focused codes, used in conjunction with PSK and QAM signaling, can provide more than 1.0 dB of additional coding gain when compared with Reed- Solomon codes for small blocklengths.Item The Reliability of Systems with Two Levels of Fault Tolerance: The Return of the "Birthday Surprise"(1990) Fuja, Tom E.; Yang, G.C.; ISRThis paper considers the reliability of systems that employ fault tolerance at two different hierarchical levels. Specifically, it assumes the system consists of a two-dimensional array of components. Each component is reliable as long as it has been afflicted by no more than t faults; when t + 1 faults occur in a particular component, the component ceases to be reliable. Furthermore, the system remains operative as long no more than one component in any row is unreliable. By generalizing the techniques used to analyze the well-known "birthday surprise" problem of applied probability, we derive an approximation to the average number of faults needed until the systems fails. Applications include random access memory systems with chip-level and board-level coding as well as fault-tolerant systolic arrays.