Search

In this concise paper, several coding schemes are proposed for transmitting digital information over a cable with dc cutoff. The codes are composed of information digits and balance digits determined by the weight of the former. It is shown that the encoding and decoding circuits are quite simple, and that the dc component of the codes is negligibly small. Furthermore, the lowfrequency components of the spectrum can be made much smaller by changing the balance digit positions. Exploiting the fact that the weight of almost all codes is zero, and using the coding rule presented, block synchronization can be easily obtained and most transmission errors can be detected.

The question of the interference between the reception and production of speech is basic to an understanding of the processes involved in simultaneous translation. This paper reports an experiment designed to throw light on this problem by controlling the level of interference between decoding and encoding speech using hesitancy as an indicator of interference. This proved effective in spotting the levels at which interference takes place. Encoding without processing did not interfere with the monitoring of even highly complex intellectual material, but encoding involving complex processing did so in proportion to the hesitancy of the input. Such encoding was facilitated at the end of the monitored sentences and inhibited while they were being monitored.

The properties of various decoding methods of results obtained by a correlation chopper are analysed. A new method of diminishing the background was demonstrated. Some conclusions leading to construction of new devices are presented.

It has been proposed that syntactical information be used as an aid in error detection, location, and correction. In the present paper the minimum distance syntactical decoding algorithm of Souza and Scholtz is improved with the use of sequential decoding techniques. Fano's algorithm is adapted to the syntactical case; simulation results show the drastic reduction in number of backtrackings afforded by the new algorithm. Comments are made on the results obtained, their implications, and topics for future research.

We consider the use of an (n, k) lineastock code over a channel from the viewpoint of a mean-square error criterion. The code is over a finite field GF(q) and the data to be transmitted have a natural q-adic association with the first zk integers. It is assumed that the transition probabilities of the channel satisfy an additive property. Optimum performance is judged by the mean-square of the overall error between input and output. On the basis of this criterion, we determine the optimum encoding rule and standard array decoding rule. Our analysis and synthesis of the coding rules employ the Fourier transforms of the channel transition probabilities. The optimum parameters of these rules are determined in the transform domain. The optimum decoder configuration for a rate k/n code resembles a bank of k generalized bandpass filters and is similar to a digital filter. It uses complex-valued arithmetic operations as opposed to finite field operations. The decoding system can efficiently employ fast transform techniques. Decoder storage requirements are also considered.

Gallager in 1965 IEEE Trans. Inform. Theory IT-11, 3) gave an elegant proof of coding theorem and obtained an upper bound over the probability of error in terms of reliability function. Its dual has recently been proved by Arimoto [(1973), IEEE Trans. Inform. Theory 19, 357]. We have modified the decoding scheme by bringing in the distortion. This provides an upper bound over distortion due to error when rate distortion function is less than capacity. When rate distortion function is above capacity a lower bound on distortion due to error gives the dual for code words of any block length.

In this paper a method is proposed for the determination of the correctable and detectable errors number, which ensures an optimum compromise between the incorrect decoding probability and the transmission rate. The method is based on the fact that by decreasing the correctable errors number and increasing the detectable errors number, both the incorrect decoding probability and transmission rate are reduced. Among the types of problems which can be solved by this method the most interesting is that of adapting the decoder to the transmission channel. In this paper the binary symmetrical channel is considered, but for other types of channels similar results can also be obtained.

A general purpose communication processor is investigated as a vehicle for decoding two specific classes of cyclic codes having properties appropriate for voice grade data communication channels. First, a model of a processor is described, and then it is used in conjunction with two cost metrics to measure the complexity of programming the decoding functions. No special Galois field (GF) arithmetic instructions are used. For decoding both Bose-Chadhuri-Hocquenghem (BCH) and Fire codes, a method which allows the encoding program to be used in the initial steps of decoding is given and evaluated. The evaluation indicates that both encoding and decoding, for voice grade data communication facilities, can be done in contemporary communication processors with core storage in the 1000 word range and instruction cycles in the microsecond range. In addition, the results show how the cost metrics vary with parameters such as the block length, the number of errors or the burst length correctable, and the block error probability introduced by the channel. Other conclusions, such as the areas in which significant improvements are needed and in which hardware assist can improve performance are drawn from data giving the relative costs of the elements of the decoding process.

Three-dimensional objects are coded using a non-redundant distribution of X-ray sources. The deconvolution of the image is performed by means of an incoherent optical processing system using a zoom-lens and a point-hologram. The method is capable of decoding the layers of the original object starting with a self-luminous image generated for example by an X-ray image intensifier tube.

An analog-digital hybrid decoder which combines amplitude and duration threshold detection and bipolar violation sensing capabilities for decoding bipolar signals is described. The main features of the decoder are: 1) a preamplifier with automatic gain control (AGC), 2) amplitude and duration threshold detectors, 3) a bipolar violation sensor, and 4) a unipolar pulse generator. The decoder is extremely robust and is self-synchronizing. If, during operation, burst errors occur, introducing bipolar violations in the received signal, the decoder decides that, where a violation has occurred, a binary "0" was transmitted. If, for some reason, the decoder is perturbed from its synchronous condition, it requires at most 1-b duration to reacquire synchronization. That is, the decoded message contains at most one erroneous bit.

This paper shows that several transmitters operating in an additive white Gaussian noise environment can send at rates strictly dominating time-multiplex and frequency-multiplex rates by use of a superposition scheme that pools the time, bandwidth, and power allocations of the transmitters. This pooling can be achieved without cooperative action, except for agreement on the actual rate of transmission each transmitter will allow itself. The superposition scheme involves subtraction from the received signal of the estimated signals sent by the other transmitters, followed by decoding of the intended signal. This scheme has been shown to be optimal. We conclude that present methods of allocating different frequency bands to different transmitters are necessarily suboptimal.

This paper describes a BCD decoder for binary counters in which the conventional diode decoding matrix is simplified by the combination of base and emitter switching of the output transistors. The resulting matrix contains only nine diodes. This arrangement is considered more economical in the use of components and space. A memory circuit incorporating bistables and gate is also described.

This paper discusses two ways of compressing seismic data prior to long‐distance transmission for display. A Walsh transform technique and an analogous time‐domain method eliminate redundant seismic information allowing data sets to be compressed with little visual degradation. The basic approach consists of using an average 3-bit code to describe data in such a way as to minimize information loss; the method also uses the Walsh transform to achieve further compaction through sequency bandlimiting. A second technique is entirely a time‐domain operation and does not use transforms. The Walsh method, however, produces larger compression ratios than the time technique before serious image degradation occurs. Both schemes have six basic parts: bandlimiting, quantization, encoding, decoding, interpolation, and band‐pass filtering; they differ only in band limiting and interpolation. Band limiting sequencies in the Walsh domain is very similar to, but not the same as, alias filtering and resampling in time. Reducing Walsh bandwidths by some power of two has a time‐domain implementation consisting of an averaging procedure with subsequent resampling, while the inverse Walsh transform step can be viewed as a means of interpolating in the time domain. The convergence properties of three Rademacher derived transforms—Hadamard, Paley, and Walsh—are studied with regard to exploration seismic data. Hadamard energy has been found to be uniformly distributed over its entire spectrum, whereas Walsh and Paley transforms concentrate about 80 percent of the total energy into a major lobe occupying about 15 percent of the total bandwidth (2 msec sampling). Smaller minor lobes containing the remaining 20 percent are discarded while bandlimiting. The major lobe energy suffices for many seismic applications such as VA/VD plot displays. Optimum quantization and encoding of major lobe energy results in an overall 28:1 compression factor for 12 bit data sampled every 2 msec. Analogous time domain compression, on the other hand, only achieves a 16:1 reduction because of the power of two restriction imposed by the resampling and averaging process.

For any alphabet A of size Q there exists error correction codes of length n , dimension k , and minimum distance ( n − k ) (Notation ( n, k ; n − k codes)) under the following conditions: Let K be a finite field containing p r elements. If I = p r − Q > 0 then n can be up to length p r for ( n − k ) p r / I . Encoding and decoding operations are performed algebraically in the field K which contains an imbedding of the alphabet A . Consequently, alphabets A with size Q = p r − 1 are encodable up to length p r with distance d less than p r − 1. The English language, the decimal integers and the alpha-numerics fall into this class. Many binary k -tuple codes can be translated into prime field codes, so computation may be affected using ordinary standard arithmetic operations.

A search algorithm is described to decode long binary block codes of any rate for the memoryless binary input J -ary output channel. It can be used directly to perform maximum-likelihood decoding or in a constrained version that gives considerably fewer searches at a small sacrifice in performance. Simulation results are given for a rate-l/2 code of length 128 and minimum Hamming distance 22 on the quantized Gaussian channel.

A new look is taken at maximum-likelihood sequence estimation in the presence of intersymbol interference. A uniform receiver structure for linear carrier-modulated data-transmission systems is derived which for decision making uses a modified version of the Viterbi algorithm. The algorithm operates directly on the output signal of a complex matched filter and, in contrast to the original algorithm, requires no squaring operations; only multiplications by discrete pulse-amplitude values are needed. Decoding of redundantly coded sequences is included in the consideration. The reason and limits for the superior error performance of the receiver over a conventional receiver employing zero-forcing equalization and symbol-by-symbol decision making are explained. An adjustment algorithm for jointly approximating the matched filter by a transversal filter, estimating intersymbol interference present at the transversal filter output, and controlling the demodulating carrier phase and the sample timing, is presented.

Several techniques are developed for digital color decoding of NTSC television signals pulse-code modulated at 10.7-MHz rates (three times the color subcarrier frequency) and 14.3-MHz rates (four times the color subcarrier frequency). Digital comb filtering is also explored as a way to achieve superior color decoding. Encoding PCM NTSC television at the 14.3-MHz rate was found to afford the best algorithms for color decoding. A different PCM technique called Phase Alternating Line Encoding (PALE) permits encoding at 10.7 MHz and allows effective digital comb filtering and good color decoding. In the PALE technique, the phase of the 10.7-MHz digital encode command signal is inverted on adjacent television lines. Straight PCM encoding at 10.7 MHz is a poor third choice for comb filtering and color decoding applications.

Forney's generalization of maximum likelihood decoding scheme takes care of erasures. From a tactical point of view it may be desired to consider multiple decoding schemes. This problem for a discrete memoryless channel has been handled in this paper and bounds on probability of error and erasure have been derived after modifying Forney's scheme for multiple decoders.

Algorithms are described for estimating carrier phase by a maximum-likelihood procedure similar to the Viterbi algorithm for decoding a digital sequence. These algorithms avoid the constraint of physical realizability imposed by a phase-locked loop and allow a processing lag in estimation. An approximate analysis suggests that threshold extension can be achieved thereby. Computer simulations demonstrate the improved performance for demodulation of FM and for tracking of phase modulation due to dynamic maneuvers.

The area of static MOS memory cells is reduced by avoiding crossovers in the flip-flop, and by selecting the cell by a diode. Such cells have been realized in epitaxial silicon films on insulators (ESFI) with complementary transistors, diodes, and high-rated load resistors; the cell areas can be as small as 1500 /spl mu/m/SUP 2/ (2.4 mil/SUP 2/), and are the smallest areas of static MOS memory cells known so far. The static and dynamic behavior of these cells are discussed, as well as their behavior in a large-scale integrated (LSI) circuit; for this purpose an exploratory memory with 4096 bits and with simple decoding and sensing circuitry has been realized on an area of 3.5/spl times/4.2 mm (140/spl times/170 mils). Taking into account the measured data, an ESFI MOS memory circuit shows a better performance in speed and power dissipation than dynamic MOS memories, but its principal advantage is the static operation mode.

Insight into the structure of the communicator's lexicon is claimed through a major variation on the classical “semantic generalization” paradigm. Primarily, the variation consists of the investigation of verbal generalization in encoding rather than decoding, and the simultaneous consideration of three generalization types—semantic, phonological, and syntactic. The results provide evidence of a lexicon organized upon a semantic‐phonological‐syntactic hierarchy.

In this paper we develop a simple encoder/decoder pair which utilizes the natural redundancy of a source for error detection. It does so with no loss in rate of transmission and with only minimal hardware cost.

By the use of abstract Fourier analysis on groups, the optimum mean-square-error decoding rule is developed for a fixed block code. The optimum one-to-one coding role to be used with this optimum decoder is derived, and a procedure for simultaneous optimization over both encoding and decoding rules is given. It is shown that there is a linear encoding rule which is optimum. A system which implements the optimum decoding rule is outlined. The major difference between this work and others involving coding for mean-square error is that the decoding rule developed here is a mapping from binary n -tuples directly into the real numbers with the optimization being over all possible mappings into the real numbers. As such the system developed here replaces both the error-correction and digital-to-analog conversion components used in most numerical data transmission systems.

An adaptive-control procedure is described which is intended to improve both acoustic analysis and linguistic decoding in automatic recognition of continuous speech by bringing into agreement data available at each of these stages. Specifically, hypotheses are formed by the decoder concerning the phonetic transcription derived during acoustic analysis. The procedure then accesses and utilizes relevant acoustic data in an attempt to verify or reject these hypotheses. Depending on the success of such attempts, actions are taken to constrain the decoding in subsequent processing iterations. Preliminary results are presented and discussed.

The organization of a particular computer is described at a level of detail suitable for classroom presentation at an introductory level. The computer consists of several units which manipulate and store data, a bus structure connecting them, and a microprogramming mechanism to control their operation. Both instruction decoding and interpretation are determined by the microprogram. The microprogram for a single-address computer is given as an example; the student is asked to redo the microprogram to implement stack instructions or some other sequential instructions of his choice. An XPL program which (1) reads a microprogram, then (2) reads a program, then (3) executes the program with a run-time trace is presented in the appendices.

An all-bubble text-editing system configuration is described, which is simpler and more versatile than the more conventional systems typically composed of a mechanical-access magnetic storage, a semiconductor buffer, and semiconductor editing shift-registers. In addition to storage and text editing, bubble devices are also proposed to implement address decoding, character encoding, and timing signal initiation.

The optimum procedure for locating a sync word periodically inserted in uncoded binary data received over a binary symmetric channel is based on the Hamming or bit distance metric. This concise paper addresses the corresponding frame-sync problem for biorthogonally coded data transmitted over the additive white Gaussian noise (AWGN) channel. For conceptual convenience, the k -bit words from the decoder output are treated as "super symbols" from an alphabet of dimension 2k. It is argued that the optimum sync-word search over the decoded data stream is based on a supersymbol distance rule matched to the properties of the biorthogonally coded transmissions over the noisy channel. An optimum frame-sync acquisition algorithm based on this distance rule is formulated, and its performance is investigated. As an example, the performance of this optimum frame-sync algorithm is contrasted analytically with that of a Hamming distance algorithm operating on decoded (32, 6) biorthogonal data, a case of interest to some recent unmanned American space missions.

A nonredundant distribution of ten point sources is used for coded aperture imaging. The coded image of a three-dimensional X-ray object is decoded by means of an incoherent projection system in all its layers. This decoding process avoids all the adjustment problems of coherent processing systems.

Sternberg's (1969) model of memory scanning processes is considered to be insufficient for verbal material. In Sternberg's model no considerations are given to coding and decoding processes which are relevant for verbal material. Usually Ss will represent letter strings of words as one unit with a specific meaning. If Sternberg's model should be valid for verbal material the time for coding and decoding of the memorized material has to be considered in addition to the time of coding the test stimulus, comparing the test item with the items of the memorized list and responding. Experimental data with different tasks to find a letter or a word in a list of words or a letter in a word can be explained adequately if coding and decoding processes for words are considered in the Sternberg model.

Many cyclic codes are generated by polynomials possessing more than one set of consecutive roots. Thus more than one set of syndrome sequences are available for decoding. In this correspondence, a decoding method based on Berlekamp's iterative algorithm is presented which makes use of the multiple sets of syndrome sequences for decoding such cyclic codes beyond the BCH bound.

Most modern computers with very few exceptions operate on the binary number system, This paper suggests a new generation of computer systems capable of performing computations in many number systems. At the present, a modern computer handles numbers other than binary through encoding prior to performing the arithmetic operations. The converting processes of encoding and decoding are both wasteful and time consuming. The proposed system is able to carry out computations in a given radix without conversions. In order to operate on a specific number system a radix control can be preset to the desired value, the computer is then converted instantly to be of that radix. In general, a number system is formed basically from counting with proper carry or carries to be generated when a desired radix is reached. High speed pulse counting with a controllable and variable carry producing mechanism is thus the most direct and efficient approach for the implementation of a variable radix computer system. In essence, a ...

The testing of binary hypotheses is developed from an information-theoretic point of view, and the asymptotic performance of optimum hypothesis testers is developed in exact analogy to the asymptotic performance of optimum channel codes. The discrimination, introduced by Kullback, is developed in a role analogous to that of mutual information in channel coding theory. Based on the discrimination, an error-exponent function e(r) is defined. This function is found to describe the behavior of optimum hypothesis testers asymptotically with block length. Next, mutual information is introduced as a minimum of a set of discriminations. This approach has later coding significance. The channel reliability-rate function E(R) is defined in terms of discrimination, and a number of its mathematical properties developed. Sphere-packing-like bounds are developed in a relatively straightforward and intuitive manner by relating e(r) and E (R) . This ties together the aforementioned developments and gives a lower bound in terms of a hypothesis testing model. The result is valid for discrete or continuous probability distributions. The discrimination function is also used to define a source code reliability-rate function. This function allows a simpler proof of the source coding theorem and also bounds the code performance as a function of block length, thereby providing the source coding analog of E (R) .

Although coherent phase-shift keying (CPSK) is an efficient means of transmitting digital signals over carrier systems, it has not enjoyed widespread use at microwave and millimeter wavelengths because of the difficulty of recovering an accurate reference carrier for coherent detection. In this paper, a system is described which requires only a narrow-band phase-locked-oscillator filter for reference carrier recovery. This is accomplished by block-coding and decoding the pulse sequence at the terminals; the recovery of a baseband timing wave is also facilitated by the coding process. It is also shown that: (i) for an arbitrary random input sequence, accurate carrier recovery cannot be achieved with just a narrow-band filter, (ii) for the system described, any input pulse sequence is acceptable, and (iii) there is a maximum error in the phase of the recovered reference carrier which can be controlled by choosing the number of pulses in the coding block and the bandwidth of the recovery filter.

This paper presents the best obtainable random coding and expurgated upper bounds on the probabilities of undetectable error, of t -order failure (advance to depth t into an incorrect subset), and of likelihood rise in the incorrect subset, applicable to sequential decoding when the metric bias G is arbitrary. Upper bounds on the Pareto exponent are also presented. The G -values optimizing each of the parameters of interest are determined, and are shown to lie in intervals that in general have nonzero widths. The G -optimal expurgated bound on undetectable error is shown to agree with that for maximum likelihood decoding of convolutional codes, and that on failure agrees with the block code expurgated bound. Included are curves evaluating the bounds for interesting choices of G and SNR for a binary-input quantized-output Gaussian additive noise channel.

A recursive procedure is derived for decoding of rate R = 1/n binary convolutional codes which minimizes the probability of the individual decoding decisions for each information bit, subject to the constraint that the decoding delay be limited to Δ branches. This new decoding algorithm is similar to, but somewhat more complex than, the Viterbi decoding algorithm. A "real-time," i.e., fixed decoding delay, version of the Viterbi algorithm is also developed and used for comparison to the new algorithm on simulated channels. It is shown that the new algorithm offers advantages over Viterbi decoding in soft-decision applications, such as in the inner coding system for concatenated coding.

Sequential decoding has been found to be an efficient means of communicating at low undetected error rates from deep space probes, but another failure mechanism known as erasure or computational overflow remains a significant problem. The erasure of a block occurs when the decoder has not finished decoding that block at the time that it must be output. The erasure rate can be unacceptably high even when the decoder is spending over half of its time idly awaiting incoming data. By drawing upon analogies in computer time sharing, this concise paper develops a buffer-management strategy which reduces the decoder idle time to a negligible level, and therefore improves the erasure probability of a sequential decoder. For a decoder with a speed advantage of ten and a buffer size of ten blocks, operating at an erasure rate of 10-2, use of this buffer-management strategy reduces the erasure rate to less than 10-4.

The first part of the paper reports an investigation of the effects of the concreteness-imagery (C-I) value of stimuli and responses on the long-term retention of paired-associate lists. With degree of learning equated, the measures of retention after a 1-week interval showed a significant interaction of Stimulus by Response C-I: When the responses had a high value, recall was substantially better with low than with high stimuli; when the responses were low, there was no reliable difference as a function of stimulus value. Recall was best when abstract stimuli were paired with concrete responses. The second part of the paper is addressed to some current issues in the analysis of coding processes. Major emphasis is placed on the experimental and theoretical differentiation of encoding and decoding processes.

An adaptive decoding technique called burst trapping is presented to correct both random and burst errors. Two decoding algorithms are used, one for random errors, and the other for bursts. The former is based on a conventional correction technique, the latter utilizes an encoding procedure for which each information digit appears twice in the data stream, first unchanged, and second combined with (addition modulo 2 ) a check digit of a widely separated later block. Whenever the number of errors within a code block are detected to be too large to correct with the random-error-correcting algorithm, the burst-correcting algorithm corrects these errors by recovering the information from later blocks where it appears in combination with check digits. It is shown that the scheme requires very limited guard space and has limited error propagation. Furthermore, the storage requirement is even smaller than the guard space. This is the only known coding system that has this desirable feature. Results of simulation of such codes over telephone channels indicate that the performance of such codes, when compared with interleaved block codes, offers better results at significantly lower cost.

The performance of a sequential decoder on data transmitted on a spacecraft link was demonstrated on February 26, 1968, culminating a series of experiments utilizing Lunar Orbiter V and the Deep Space Net (DSN) Echo station. It was demonstrated that sequential decoding can perform on a spacecraftlink as well as was predicted by theoretical results and laboratory experiments. Performance is significantly better than that of practical block codes. For example, an erasure probability of 10^{-4} can be attained using sequential decoding with 2 dB less signal-to-noise ratio than required to attain an error probability of 10^{-4} using a (32,6) biorthogonal code and maximum-likelihood decoding.

The subjective error in decoding a circular diagram is a substantial component of the total circular-diagram measurement error. It was found that in measuring roundness irregularities below 1 μ, which corresponds to shape precision I, II, and III of GOST (All-Union State Standard) 10356-63, the subjective decoding error may attain 50% of the measured quantity. This error in measuring roundness irregularities which approach 1μ can be substantially reduced by providing additional expansion steps. The subjective decoding error consists of the error in finding the center and diameter of the basic circumference and of the error in estimating the position of the most distant point from the basic circumference. These are random errors. Numerical characteristics of their statistical distribution have been established for reading errors at ¯So=±0.06 templet divisions, for finding the position of the center at ¯Sc=±0.2 templet divisions, and for determining the diameter of the basic circumference at Sd=+-0.09 templet divisions. It has been established that the decoding of circular diagrams entails the operator in the complicated visual problem of orientation by means of templet scale lines and of tracing one of these lines. His task can be greatly facilitated by altering the design of the templet.

The design of a communications system consisting of a sequential encoder-decoder, working in conjunction with a modulation-detection system is considered from the point of view of high-information transmission efficiency. Emphasis is placed on M orthogonal signal modulation and a scheme known as list-of- l quantization. The results of a computer study of the computational behavior of the sequential decoder are described and used to predict buffer memory overflow probability. The described design procedure allows prediction of system performance to within a fraction of a decibel. A practical sequential decoder and a list-of- l modulation-detection system of reasonable complexity, can achieve performance on a white Gaussian channel to within 4.5 dB of the Shannon limit with coherent reception and to within 7 dB with incoherent reception.

This paper treats the problem of compressing binary strings of fixed length into shorter strings of fixed length. Constraints are assumed with respect to the maximum number of ones which can occur in the input binary string and on the memory available for encoding or decoding using table look-up operations. Bounds and coding techniques are presented. There appear to be many applications to the information sciences and especially to memory utilization in digital computers and to information retrieval.

A trend toward development of nonbinary digital transmission systems has been growing for several years. Much effort has been expended on attempts to optimize digital transmission efficiency, either in terms of speed, reliability, or some other parameter.

Presentation of results concerning the performance of a family of binary systematic codes of arbitrary size, correcting bursts of considerable length and/or "random" errors. The basic idea of these codes is due to C. Hobbs of the Air Force Cambridge Research Center. For the codes of two sub-families, practical decoding schemes are given. Also formulated are results concerning the use of these codes with erasure channels.