This paper describes a concatenated code method where the outer decoder hypothesizes possible block symbol values for the inner code to make a likelihood retest from its original soft information. These hypotheses come from low density check sets where the probability is significant that there is only one error in the check set, whose value would be the syndrome for that check. The method has an advantage over pure verifications in converting errors into erasures. Also, it is shown that, if the inner decoder can supply a list of two decisions for each symbol, the decoding method, for large first choice symbol error probability p, allows reliable communication at rates substantially exceeding the (1-p) log2Q QSC per symbol channel capacity with b-bit symbols.

In this paper, a new method is described which builds on Mitzenmacher's idea of adding a different pseudorandom number to each packet to help decode packet-symbol low-density codes, with deletions, errors, and out-of-order reception, without sequence numbers. The new method has lower decoding complexity than the original method. The most basic form of the new method applies to any parity-check code structure, but is limited to a rather small number of packets in the code. Decoding success is slightly inferior to an ideal erasure channel, which would require sequence numbering and error detection in each packet. Error detection is needed only for the whole code, amounting to usually less than one bit per packet symbol. Moreover, if error detection can resolve one of a small number of alternatives, the ordered case performs almost as well as the ideal erasure channel. Ways are shown to modify the basic algorithm for use with long codes, possibly approaching the erasure channel capacity limit.

In this communication, simple methods are shown for correcting bursts of large size and bursts combined with random errors using vector symbols and primarily vector XOR and feedback shift register operations. One result is that any (n, k) cyclic code with minimum distance > 2 can correct all full vector symbol error bursts of length n-k-1 or less if the error vectors are linearly independent. If the bursts are not full but contain some error-free components, the capability of correcting bursts up to n-k or less is code dependent. Also, vector symbol decoding with Reed-Solomon component codes can correct, very simply, with probability ges 1- n(n - k)2-r, all cases of e les n - k - 1 r-bit random errors in any cyclic span of length les n - k. The techniques often work when there is linear dependence. In cases where most errors are in a burst but a small number of errors are outside, the solution, given error-correcting capability, can be broken down into a simple solution for the small number of outside errors, followed by a simple subtraction to reveal all the error values in the burst part.

This paper presents a new decoding method inspired by Mitzenmacher's idea of adding a different pseudo-random number to each packet, in a packet-symbol (n, k) code, for verification-based decoding low density codes with packet deletions or errors, or out-of-order receptions, and no sequence numbers. The new method has less decoding complexity and is not restricted to low density codes. In multipath reception, the same packet may be received more than once, correctly or incorrectly, packets may be received out of order, or with error. Despite this and despite using no sequence number overhead and very limited error detection overhead, the decoder can decode the packet-based code and re-order the data as long as the errors and deletions do not come within 2 of covering the positions of any code word. If order is preserved, the constraint is not to come within one of covering any code word. Also, it is shown how convolutional codes can further simplify decoding.

Wireless ad-hoc sensor networks are being developed to carry out tasks such as target detection and tracking, environment monitoring, and data collection across the area of deployment. We explore the problem of using sensor networks to detect and track continuous objects, such as wild fire and bio-chemical material. The continuous objects are different from traditional one or many individual targets in that they are continuously distributed across a region and usually occupy a large area. These continuous objects tend to diffuse, increase in size, change in shape, or even split into multiple relatively smaller continuous objects. The fusion and dissemination of local boundary information becomes a very challenging problem. In the paper, we propose a dynamic cluster-based structure to track the movement of boundaries and facilitate the fusion and dissemination of boundary information in a sensor network.

Prior work showed the ability of a randomly chosen outer code of a concatenated code to correct large numbers of nonbinary symbol errors in a simple manner, provided that the error symbols as vectors are linearly independent. This paper extends the technique in two ways: 1) it is shown how to correct a large class of dependent errors with little additional complexity; and 2) if the inner code supplies a list of two (or more) candidates in some or all decisions, a slightly modified vector symbol decoder can directly reveal most correct alternatives, allowing more powerful and often simpler correction.

We present a new technique for locating corrupted page copies, outdated page copies, and missing page copies in multiple replicated large file copies. We present four communication models and four communication protocols to be used in this technique. These four protocols are classified according to using or not using a coordinator site, groups, and/or a master signature. Whereas, other previous works consider locating only corrupted page copies, our protocols can locate outdated page copies and missing page copies as well as corrupted page copies. In addition, whereas other previous works are based on majority rule to determine the correct copy, our protocols are not. The performances of these protocols are measured in terms of the number of transmissions and the number of transmitted signatures. We compare these performances with one another and, also, compare them to the performances of other previous works.

The average codeword success probability of the majority-logic-like vector symbol (MLLVS) code is derived for the following two cases: (1) single-pass decoding and (2) upper bound of multipass decoding, when the received word has more than (J-1) symbol errors, where J is the number of check sum equations. The MLLVS code has been simulated by Metzner (1996), and it was concluded that the average error correcting capability of MLLVS codes exceed the decoding capability of Reed-Solomon codes, but is achieved with less complexity. Additionally, for codes that have larger structures, the error correcting capability is sustained even further with a high probability of decoding success through multipass decoding procedures. The mathematical derivations of the error correction performance beyond (J-1) symbol errors serve as theoretical proof of the MLLVS code error correcting capability that was shown only through simulation results until now by Metzner. One characteristic feature of this derivation is that it does not assume any specific inner code usage, enabling the derived decoding probability equations to be easily applied to any inner code selected, of a concatenated coding structure.

Majority-logic-like decoding is an outer concatenated code decoding technique using the structure of a binary majority logic code. It is shown that it is easy to adapt such a technique to handle the case where the decoder is given an ordered list of two or more prospective candidates for each inner code symbol. Large reductions in failure probability can be achieved. Simulation results are shown for both block and convolutional codes. Punctured convolutional codes allow a convenient flexibility of rate while retaining high decoding power. For example, a (856, 500) terminated convolutional code with an average of 180 random first-choice symbol errors can correct all the errors in a simple manner about 97% of the time, with the aid of second-choice values. A (856, 500) maximum-distance block code could correct only up to 178 errors based on guaranteed correction capability and would be extremely complex.

Previously (see ibid., vol.41, no.9, p.1364, 1993), the capture phenomenon in nonbit-synchronous mobile packet radio networks for binary phase shift keying (BPSK) and differential phase shift keying (DPSK) modulation was investigated. Most of the analysis is correct. Unfortunately, the mathematical expressions for state transition probabilities, adopted from previous work, have errors. Over a decade, these mathematical formulas have been used repeatedly to analyze various capture models with a finite number of users in the traditional slotted ALOHA system. In this note, we present a corrected version of the state transition probabilities.

The use of the structure of one-step decodable majority logic codes for enhanced and simplified vector symbol decoding, such as outer code decoding of concatenated codes, is proposed. For J equations checking a particular symbol, the technique to be described almost always corrects the symbol if there are J-1 or fewer symbol errors, and often corrects cases of far more than J symbol errors. Ordinarily, majority level decoding with J equations for a symbol corrects the symbol in all cases where there are up to [J/2] errors. The decoding power is comparable to Reed-Solomon codes, but decoding is simpler than for Reed-Solomon codes.

Incremental redundancy transmission is an efficient data communication technique in a frequency hopping code division multiple access system. However, there are some difficulties in practical implementation of this technique such as synchronization of packets of different sizes and identification between regular and subpackets. This paper describes these problems and suggests practical solutions to avoid the loss of synchronization and decoding ambiguity during transmission of messages.>

The author improves on some previous work involving data transfer to find the location of disagreements between two or more large remote data files. Some procedures that permit a significant reduction in the number of back-and-forth interchanges are described, one of which significantly reduces the total amount of data transfer required. The older scheme could locate a disagreeing page with an extremely high degree of confidence more than one interchange. The new procedures require at most one back-and-forth interchange for each disagreeing page, often considerably less.>

An algorithm for improving the stability and throughput of a frequency hopping code-division multiple-access system (FH-CDMA) is presented. The algorithm includes a multiple block transmission with error-detection block(s) and a logical AND-operation between previously received (erroneous but saved) data, and retransmitted data. The packet success probability of the new algorithm is formulated and the improvement in stability is shown in terms of the proportion of retransmission users in the system under various conditions, including the new packet generation probability, retransmission probability, different signal-to-noise ratio in the channel, and the number of blocks in a packet. The average drift of retransmission users and the analysis of the expected number of retransmissions were used to evaluate the stability performance of the retransmission strategy.>

The problem of increasing the probability of successfully transmitting a data packet during a meteor burst is considered. It is shown how the ordering of redundant information can be chosen to increase success probability. Two simple rate 1/2 coding schemes amenable to soft decision decoding are introduced. It is found that these codes provide considerable additional improvement in the probability of successful transmission. One of the codes achieves significantly better performance than a hard decision (31, 15) Reed-Solomon code proposed previously.>

Code symbols are treated as vectors in an r-dimensional vector space F/sup r/ over a field F. Given any (n, k) linear block code over F with minimum distance d, it is possible to derive an (n, k) code with symbols over F/sup r/, also with minimum distance d, which can correct any pattern of d-2 or fewer symbol errors for which the symbol errors as vectors are linearly independent. This is about twice the bound on the number of errors guaranteed to be correctable. Furthermore, if the error vectors are linearly dependent and d-2 or fewer in number, the existence of dependence can always be detected. A decoding techinque is described for which complexity increases no greater than as n/sup 3/, for any choice of code. For the two applications considered, situations are described where the probability of the error patterns being linearly dependent decreases exponentially with r.>

This paper investigates memory and selective repeat ARQ techniques when channels in both directions are very noisy. It demonstrates that a difficulty arises when memory ARQ is used in these situations, and proposes a remedy-the similarity test. The paper considers a combination of both memory ARQ techniques where an unacknowledged block is retransmitted exactly as before, and modified memory ARQ where alternate transmissions together form a rate 1/2 code. The following items are featured. 1) Discussion and analysis of the similarity test. 2) A memory ARQ technique which employs double null zone reception and 3 bits of past information storage per binary digit. 3) For modified memory ARQ procedures, a discussion of how to resolve problems of confusing the identity of the two halves of the rate 1/2 code used.

This paper deals with the problem of optimizing the decisions as to when to schedule transmissions of messages under varying channel conditions. A cost function is minimized which is a sum of delay cost and resource cost. An exponential delay cost function is utilized which is unconventional, but has some realistic qualities as well as mathematical convenience. Most of the analysis is based on using the two-state Markov model of channel conditions. However, to improve realism, the bad channel state is assumed in some cases to have several modes of different expected durations, but the mode is not known to the user. Results are derived for two cases. One case is that of a single, lightly loaded two-state channel where a message arrives during a bad state. A second case is where there is time sharing of transmission over different channels where conditions on the different channels vary differently.

A recent paper by Calo and Easton proposes a broadcast protocol for identical file transfers toMdifferent sites wherein a large block of transmitted data is divided intoNframes ofBbits each, and in a second transmission cycle all frames not acknowledged by all sites are retransmitted. This paper shows several versions of a different technique which can result in better efficiency. In the technique, additional frames sent are not exact replicas of initially unacknowledged frames, but are chosen to provide additional information to all sites having one or more nondecodable frames. New frames are sent to provide additional information until all sites acknowledge the entire block.

This paper suggests a technique applicable to chip-synchronous frequency-hopping MFSK multiaccess communication whereby each user has some high-power-level slots and some low-power-level slots. The optimum proportion of high-power slots is slightly less than1/ewhereeis the natural logarithm base. For this optimum proportion, the data rate efficiency is improved by about 50 percent for fixed bit error rate in the interference-only case.

This paper proposes a parity structure for large remotely located replicated data files. The parity structure can accomplish the following objectives. 1) Ascertain with a high degree of confidence whether two or more files are identical, using a very small amount of communication. 2) If there is disagreement between two files, the disagreeing portion can be located simply and with a small amount of communication. 3) Memory faults within each individual file can be detected simply and with high probability.

A memory protection technique is described in which individually code-protected memory cells are supplemented with redundant memory cells derived from the basic cells according to the rules of a short constraint length convolutional code. The technique is found to be far more protective against faults than memory duplication. The method of clearing up faults is extremely simple—only slightly more complex than with memory duplication.

Consider the case where ann-digit block encoded word cannot be decoded reliably and a second block ofnredundant digits is sent to allow the receiver to make a new try based on the combined information received. Two classes of schemes are proposed and analyzed which give significantly better performance than is obtained by sending a repeat of the first block, yet do not require excessive decoding complexity. One approach is to consider small sub-blocks of the originaln-digit code as the data digits of a short rate one-half code. The other approach is to treat the first sending as the data digits of a systematic convolutional code of short constraint length. Comparisons are made for the white Gaussian noise channel and the erasure channel. The comparisons are limited to an assessment of the improvement gained after two sendings. Procedures using length 4 sub-blocks and using convolutional codes with constraint lengths as short as 2 or 3 digits yield considerable improvement over block retransmission. For the case of the erasure channel, a very simple decoding rule is devised for the convolutional code case.

A situation is postulated whereby the goal is to maximize the average number of bits per second reliably communicated by nonbinary block codes over a channel whose conditions are slowly varying in a largely unpredictable fashion. A feedback channel limited to block retransmission requests is assumed. It is demonstrated that repetition usually is not the best signaling technique for sequential decision making under the postulated situation. Examples of improved sequential signaling techniques are given for multilevel amplitude modulation and multiple phase modulation.

By the simple expedient of dividing users into two groups-one transmitting at high power and the other at low powerthe maximum utilization of a slotted ALOHA communication system can be increased from 36.8 percent to about 53 percent. Similar comments apply to the unslotted ALOHA case. An extension to more than two power groups also is described.

It sometimes is desirable to separate data from feedback-acknowledgment signals in a duplex communication link. An efficient technique for sending the two types of signals separately and reliably is described.

The new-word policy with decision feedback is shown to improve the efficiency of loop data communication with noisy links to the extent that the average number of loop transmissions per new word increases only linearly with the number of identically noisy links. This compares to an exponential increase in more conventional acknowledge-or-retransmit systems. Also, in the (almost) noiseless case, a greater number of word transfers per loop transmission can be achieved.

A feedback policy, denoted the "new-word policy," is described that permits reduction in the required number of repeats compared to the method commonly proposed. An expression is derived comparing the average number of transmissions required per new word.

A channel modeling technique is described that looks at the communication problem from a new viewpoint. A quantity called unfolding capacity--the capacity of a channel as it happens to unfold--is defined. A theorem is derived that proves for the assumed channel model, a feedback scheme can be devised that for sufficiently largeN, achieves arbitrarily Iow probability of error at any rate less than unfolding capacity, no matter what capacity happens to unfold. The theorem also proves that this type of performance can not be achieved without feedback.

A method of burst-error correction is presented which works for a large class of codes. Any single burst of length up to somewhat less than one half the number of check digits can be corrected. The number of decoding computations per code word is proportional to the square of the code length for long codes. The code can be chosen in a random manner, except that several trials may sometimes be necessary in order to find a suitable code.

The basic problem of transmitting information through a noisy channel in a finite time with the least error is considered. The transmitted signals are either peak or average power limited, and the interference is presumed to be additive white gaussian noise. It is shown that the optimum signals are sequences of binary waveforms resembling a(2^m -l,m)Slepian group code, the generators of which can be obtained from a modified Reed Code. An analysis is also made of near-optimum codes which allow some inequality in the distance between code words in signal space. The advantage of these near-optimum codes is that for a small sacrifice in error probability, either the information rate can be substantially increased, or the bandwidth of the system greatly reduced. The details of these sytems are given and the results show that a many-fold improvement is obtained. An instrumentation of the detector is also presented to show how the code groups at the receiver can be effectively stored as an arrangement of resistors.