SEARCH · Search NASA
Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.
Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.
The invention relates to a concatenated Reed-Solomon/convolutional encoding system consisting of a Reed-Solomon outer code and a convolutional inner code for downlink telemetry in space missions, and more particularly to a Reed-Solomon encoder with programmable interleaving of the information symbols and code correction symbols to combat error bursts in the Viterbi decoder.
A method for obtaining the complete path enumerator T(D, L, I) of a convolutional code is described. A system of algebraic equations is solved, using a new algorithm for computing determinants, to obtain T(D, L, I) for the (7,1/2) NASA standard code. Generating functions, derived from T(D, L, I) are used to upper bound Viterbi decoder error rates. This technique is currently feasible for constraint length K less than 10 codes. A practical, fast algorithm is presented for computing the leading nonzero coefficients of the generating functions used to bound the performance of constraint length K less than 20 codes. Code profiles with about 50 nonzero coefficients are obtained with this algorithm for the experimental K = 15, rate 1/4, code in the Galileo mission and for the proposed K = 15, rate 1/6, 2-dB code.
The decoding problem of multi-level block modulation codes is investigated. The hardware design of soft-decision Viterbi decoder for some short length 8-PSK block modulation codes is presented. An effective way to reduce the hardware complexity of the decoder by reducing the branch metric and path metric, using a non-uniform floating-point to integer mapping scheme, is proposed and discussed. The simulation results of the design are presented. The multi-stage decoding (MSD) of multi-level modulation codes is also investigated. The cases of soft-decision and hard-decision MSD are considered and their performance are evaluated for several codes of different lengths and different minimum squared Euclidean distances. It is shown that the soft-decision MSD reduces the decoding complexity drastically and it is suboptimum. The hard-decision MSD further simplifies the decoding while still maintaining a reasonable coding gain over the uncoded system, if the component codes are chosen properly. Finally, some basic 3-level 8-PSK modulation codes using BCH codes as component codes are constructed and their coding gains are found for hard decision multistage decoding.
The Viterbi Algorithm (VA) is optimum in the sense of being maximum likelihood for decoding codes with a trellis structure. However, since the VA is in fact an exhaustive search of the code trellis, the complexity of the VA grows exponentially with the constraint length upsilon. This limits its application to codes with small values of upsilon and relatively modest coding gains. The M-Algorithm (MA) is a limited search scheme which carries forward M paths in the trellis, all of the same length. All successors of the M paths are extended at the next trellis depth, and all but the best M of these are dropped. Since a limited search convolutional decoder will flounder indefinitely if one of the paths in storage is not the correct one, the data are usually transmitted in blocks. It has been shown that the performance of the MA approaches the VA at high signal to noise ratios (SNR's) with an M which is far less than the 2 sup upsilon states in the full trellis. Thus the MA can be used with larger values of upsilon, making larger coding gains possible at high SNR's. However, it still requires a relatively large fixed computational effort to achieve good performance.
A concatenated coded modulation scheme for error control in data communications is presented. The scheme is achieved by concatenating a Reed-Solomon outer code and a bandwidth efficient block inner code for M-ary PSK modulation. Error performance of the scheme is analyzed for an AWGN channel. It is shown that extremely high reliability can be attained by using a simple M-ary PSK modulation inner code and relatively powerful Reed-Solomon outer code. Furthermore, if an inner code of high effective rate is used, the bandwidth expansion required by the scheme due to coding will be greatly reduced. The proposed scheme is particularly effective for high speed satellite communications for large file transfer where high reliability is required. Also presented is a simple method for constructing block codes for M-ary PSK modulation. Some short M-ary PSK codes with good minimum squared Euclidean distance are constructed. These codes have trellis structure and hence can be decoded with a soft-decision Viterbi decoding algorithm.
Multi-level method is a powerful technique for constructing bandwidth efficient modulation codes. It allows the construction of modulation codes systematically with arbitrary large minimum squared Euclidean distance from component codes in conjunction with proper bits-to-signal mapping. If the component codes are chosen properly, the resultant modulation code not only has good minimum squared Euclidean distance but is also rich in structural properties such as: linear structure, phase invariant property, and trellis structure. A modulation code with linear structure has invariant distance distribution. Phase invariant property is useful in resolving carrier-phase ambiguity and ensuring rapid carrier-phase resynchronization after temporary loss of synchronization. It the component codes have trellis structure, the resultant multi-level modulation code also has trellis structure. Trellis structure allows decoding of a multi-level modulation code with the soft-decision Viterbi decoding algorithm. Furthermore, the multi-level structure allows decoding of a multi-level modulation code with the multi-stage decoding. This type of decoding reduces the decoding complexity. Multi-stage decoding is not optimum even though the decoding of each component is optimum. Based on the analysis and simulation results, the difference in error performance between the optimum decoding of the overall multi-level modulation code and the suboptimum multi-stage decoding of the code is very little, a fraction of dB loss.
The trellis structure of linear block codes (LBCs) is discussed. The state and branch complexities of a trellis diagram (TD) for a LBC is investigated. The TD with the minimum number of states is said to be minimal. The branch complexity of a minimal TD for a LBC is expressed in terms of the dimensions of specific subcodes of the given code. Then upper and lower bounds are derived on the number of states of a minimal TD for a LBC, and it is shown that a cyclic (or shortened cyclic) code is the worst in terms of the state complexity among the LBCs of the same length and dimension. Furthermore, it is shown that the structural complexity of a minimal TD for a LBC depends on the order of its bit positions. This fact suggests that an appropriate permutation of the bit positions of a code may result in an equivalent code with a much simpler minimal TD. Boolean polynomial representation of codewords of a LBC is also considered. This representation helps in study of the trellis structure of the code. Boolean polynomial representation of a code is applied to construct its minimal TD. Particularly, the construction of minimal trellises for Reed-Muller codes and the extended and permuted binary primitive BCH codes which contain Reed-Muller as subcodes is emphasized. Finally, the structural complexity of minimal trellises for the extended and permuted, and double-error-correcting BCH codes is analyzed and presented. It is shown that these codes have relatively simple trellis structure and hence can be decoded with the Viterbi decoding algorithm.
Results are reported on the performance of the Deep Space Network's frame synchronizer for the (15,1/4) convolutional code after Viterbi decoding. The threshold is found that optimizes the probability of acquiring true sync within four frames using a strategy that requires next frame verification.
Channel and source coding theories are discussed. The following subject areas are covered: large constraint length convolutional codes (the Galileo code); decoder design (the big Viterbi decoder); Voyager's and Galileo's data compression scheme; current research in data compression for images; neural networks for soft decoding; neural networks for source decoding; finite-state codes; and fractals for data compression.
A model for the prediction and analysis of sensor information recorded during robotic performance of telemanipulation tasks is presented. The model uses the hidden Markov model to describe the task structure, the operator's or intelligent controller's goal structure, and the sensor signals. A methodology for constructing the model parameters based on engineering knowledge of the task is described. It is concluded that the model and its optimal state estimation algorithm, the Viterbi algorithm, are very succesful at the task of segmenting the data record into phases corresponding to subgoals of the task. The model provides a rich modeling structure within a statistical framework, which enables it to represent complex systems and be robust to real-world sensory signals.
As a demonstration of the performance capabilities of trellis codes using multidimensional signal sets, a Viterbi decoder was designed. The choice of code was based on two factors. The first factor was its application as a possible replacement for the coding scheme currently used on the Hubble Space Telescope (HST). The HST at present uses the rate 1/3 nu = 6 (with 2 (exp nu) = 64 states) convolutional code with Binary Phase Shift Keying (BPSK) modulation. With the modulator restricted to a 3 Msym/s, this implies a data rate of only 1 Mbit/s, since the bandwidth efficiency K = 1/3 bit/sym. This is a very bandwidth inefficient scheme, although the system has the advantage of simplicity and large coding gain. The basic requirement from NASA was for a scheme that has as large a K as possible. Since a satellite channel was being used, 8PSK modulation was selected. This allows a K of between 2 and 3 bit/sym. The next influencing factor was INTELSAT's intention of transmitting the SONET 155.52 Mbit/s standard data rate over the 72 MHz transponders on its satellites. This requires a bandwidth efficiency of around 2.5 bit/sym. A Reed-Solomon block code is used as an outer code to give very low bit error rates (BER). A 16 state rate 5/6, 2.5 bit/sym, 4D-8PSK trellis code was selected. This code has reasonable complexity and has a coding gain of 4.8 dB compared to uncoded 8PSK (2). This trellis code also has the advantage that it is 45 deg rotationally invariant. This means that the decoder needs only to synchronize to one of the two naturally mapped 8PSK signals in the signal set.
An analysis and discussion of a bandwidth efficient multi-level/multi-stage block coded modulation technique called Least Reliable Bits Coding (LRBC) is presented. LRBC uses simple multi-level component codes that provide increased error protection on increasingly unreliable modulated bits in order to maintain an overall high code rate that increases spectral efficiency. Further, soft-decision multi-stage decoding is used to make decisions on unprotected bits through corrections made on more protected bits. Using analytical expressions and tight performance bounds it is shown that LRBC can achieve increased spectral efficiency and maintain equivalent or better power efficiency compared to that of Binary Phase Shift Keying (BPSK). Bit error rates (BER) vs. channel bit energy with Additive White Gaussian Noise (AWGN) are given for a set of LRB Reed-Solomon (RS) encoded 8PSK modulation formats with an ensemble rate of 8/9. All formats exhibit a spectral efficiency of 2.67 = (log2(8))(8/9) information bps/Hz. Bit by bit coded and uncoded error probabilities with soft-decision information are determined. These are traded with with code rate to determine parameters that achieve good performance. The relative simplicity of Galois field algebra vs. the Viterbi algorithm and the availability of high speed commercial Very Large Scale Integration (VLSI) for block codes indicates that LRBC using block codes is a desirable method for high data rate implementations.
An advanced Coded Trellis Modulation (CTM) System which achieves a 2 bits/s/Hz bandwidth efficiency at an information rate of 200 Mbit/s while minimizing satellite power requirements, was developed for downlink earth station applications. The CTM system employs a high-speed rate 8/9 convolutional code with Viterbi decoding and an 8-Phase Shift Keying (PSK) modem. The minimum Euclidean distance between the modulated waveforms corresponding to the information sequences are maximized in order to maximize the noise immunity of the system. Nyquist filters with a square-root of 40 percent roll-off are used at the transmit and receive sides of the modem in order to minimize intersymbol interference, adjacent channel interference, and distortion at the nonlinear satellite power amplifier. The use of a coded system here also minimizes the effects of co-channel interference. The developed performance of the hardware system was measured to achieve within 1.5 dB from theory at a bit error rate of 5 x 10(exp -7) over an additive white Gaussian noise channel.
Source coders and channel coders are generally designed without reference to each other. This approach is justified by a famous result of Shannon's. However, there are many situations in practice in which the assumptions upon which this result is based are violated. Specifically, we examine the situation where there is residual redundancy at the source coder output. We have previously shown that this residual redundancy can be used to provide error correction using a viterbi decoder. In this paper, we present the second half of this design; the design of encoders for this situation. We show through simulation results that the proposed coders consistently outperform conventional source/channel coder pairs with gains of up to 12 dB at high probability of error.
This paper describes a 5-kilobit/s spread spectrum modem with a 1.275 mega-Hz chip rate for mobile satellite communications. We used a Viterbi decoder with a coding gain of 7.8 dB at a BER of 10(exp -5) to decrease the required receiver power. This reduces the cost of communication services. The spread spectrum technique makes the modem immune to terrestrial radio signals and keeps it from causing interference in terrestrial radio systems. A class C power amplifier reduces the modem's power consumption. To avoid nonlinear distortion caused by the amplifier, the envelope of the input signal is kept constant by adding quadrature channel signal to the BPSK signal. To simulate the worst case, we measured the modem's output spectrum using a limiting amplifier instead of the class C amplifier, and found that 99 percent of the spectral power was confined to the specified 2.55 mega-Hz bandwidth.
LRBC, a bandwidth efficient multilevel/multistage block-coded modulation technique, is analyzed. LRBC uses simple multilevel component codes that provide increased error protection on increasingly unreliable modulated bits in order to maintain an overall high code rate that increases spectral efficiency. Soft-decision multistage decoding is used to make decisions on unprotected bits through corrections made on more protected bits. Analytical expressions and tight performance bounds are used to show that LRBC can achieve increased spectral efficiency and maintain equivalent or better power efficiency compared to that of BPSK. The relative simplicity of Galois field algebra vs the Viterbi algorithm and the availability of high-speed commercial VLSI for block codes indicates that LRBC using block codes is a desirable method for high data rate implementations.
Prototype decoding system operates at 200 Mb/s. ACS (add/compare/select) gate array is highly integrated emitter-coupled-logic circuit implementing arithmetic operations essential to Viterbi decoding of convolutionally encoded data signals. Principal advantage of circuit is speed. Operates as single unit performing eight additions and finds minimum of eight sums, or operates as two independent units, each performing four additions and finding minimum of four sums. Flexibility enables application to variety of different codes. Includes built-in self-testing circuitry, enabling unit to be tested at full speed with help of only simple test fixture.
Papers on the following topics are presented: considerations of testing the Orbital Maneuvering Vehicle (OMV) system with CLASS; OMV CLASS test results (first go around); equivalent system gain available from R-S encoding versus a desire to lower the power amplifier from 25 watts to 20 watts for OMV; command word acceptance/rejection rates for OMV; a memo concerning energy-to-noise ratio for the Viterbi-BSC Channel and the impact of Manchester coding loss; and an investigation of error correcting techniques for OMV and Advanced X-ray Astrophysics Facility (AXAF).