For binary linear block codes, this letter deals with a class of decoding algorithms which utilize bounded-distance and encoding-based decodings with input sequences that are calculated from a received sequence and given test patterns. We propose a new method for selecting the test patterns by simulation. The effectiveness of the decoding algorithm whose test patterns are selected by the proposed method is also shown by simulation.

A new soft-input soft-output (SISO) decoding algorithm based on minimum distance search (MDS), called SISO-IMDS, is presented. The bit error rate of the proposed SISO decoding algorithm is almost the same as those of Max-Log-MAP and Log-MAP algorithms. Moreover, the average decoding complexity of the MDS based SISO decoding algorithm is much smaller than those of trellis-based SISO decoding algorithms. Consequently, the proposed SISO-IMDS can be applied in practical iterative decoding algorithms for a product code and a block turbo code.

We consider an iterative decoding algorithm by using algebraic decoding for non-binary codes. In the decoding algorithm, algebraic decoding are carried out with respect to successively chosen input words, called the search centers. We present a new method for selecting sequences of search centers of algebraic decoding. Over the AWGN channel using BPSK signaling, we show simulation results on the error performances of the iterative decoding algorithms whose search centers are given by the proposed method, abbreviated IAD, for Reed-Solomon codes. From the simulation results, IAD provides considerably better error performance than GMD and CGA decoding with the same number of iterations.

In this paper, a new top-down style recursive maximum likelihood decoding (MLD) using ordered statistic information is proposed. An effective termination condition is introduced.

The generalized minimum distance (GMD) and Chase (1972) decoding algorithms are some of the most important suboptimum bounded distance decoding algorithms for binary linear block codes over an additive white Gaussian noise (AWGN) channel. We compute the limitation of the ratio between the probability of decoding error for the GMD or any one of the Chase decoding algorithms and that of the maximum-likelihood (ML) decoding when the signal-to-noise ratio (SNR) approaches infinity. If the minimum Hamming distance of the code is greater than 2, the limitation is shown to be equal to 1 and thus the GMD and Chase decoding algorithms are asymptotically optimum.

We consider the binary images of (8, 5) shortened cyclic codes. The (8, 5) shortened cyclic codes have a variety of choices. We have generated about 30000 sample codes with different weight distributions. Let S/sub w/ denote the set of generated sample codes with minimum weight w. The largest minimum weight of sample codes is 8. Let A/sub w/ denote the number of codewords of weight w of a sample code. In S/sub 7/, the smallest of A/sub 7/ is 10 for 10 sample codes and the second smallest of A/sub 7/ is 11 for six sample codes. In S/sub 7/, the smallest of A/sub 8/ is 728 for a sample code and the second smallest of A/sub 8/ is 729 for a sample code. We have chosen two sample codes from each of S/sub 7/ and S/sub 8/ which have the smallest and the second smallest sums of A/sub w/ for 7/spl les/w/spl les/9 in S/sub 7/ and S/sub 8/, respectively. For the AWGN channel using BPSK signaling, we have made simulation to evaluate the decoding error probabilities by a soft-decision decoding based on ordered statistics for the chosen four sample codes at SNR 2.0 to 5.0. These error probabilities are considerably smaller than the optimum error probabilities for (64, 40) subcodes of (64, 42) Reed-Muller code.

This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.

In this article, constructions of generalized concatenated (GC) codes with good rates and distances are presented. Some of the proposed GC codes have simpler trellis complexity than Euclidean geometry (EG), Reed-Muller (RM), or Bose-Chaudhuri-Hocquenghem (BCH) codes of approximately the same rates and minimum distances, and in addition can be decoded with trellis-based multistage decoding up to their minimum distances. Several codes of the same length, dimension, and minimum distance as the best linear codes known are constructed.

This paper considers block-coded 8-phase-shift-keying (PSK) modulations for the unequal error protection (UEP) of information transmitted over Rayleigh-fading channels. Both conventional linear block codes and linear UEP (LUEP) codes are combined with a naturally labeled 8-PSK signal set, using the multilevel construction of Imai and Hirakawa (1977). Computer simulation results are presented showing that, over Rayleigh-fading channels, it is possible to improve the coding gain for the most significant bits with the use of binary LUEP codes as constituent codes, in comparison with using conventional binary linear codes alone.

This paper presents an efficient trellis-based maximum-likelihood decoding algorithm for binary linear block codes. This algorithm is recursive in nature and is devised based on the structural properties and optimum sectionalization of a code trellis. The complexity of the proposed decoding algorithm is analyzed. Numerical results show that the proposed decoding algorithm significantly reduces the decoding complexity. A recursive method for finding the optimum sectionalization of a trellis in terms of computational complexity is given.

This paper presents a method for evaluating the bit-error probability of a concatenated coding system for BPSK transmission over the AWGN channel. In the concatenated system, a linear binary block code is used as the inner code and is decoded with the soft-decision maximum likelihood decoding, and a maximum distance separable code (or its interleaved code) is used as the outer code and is decoded with a bounded distance decoding. The method is illustrated through a specific example in which the inner code is a binary (64.40.8) Reed-Muller subcode and the outer code is the NASA standard (255, 223, 33) Reed-Solomon code over GF(2/sup 8/) interleaved to a depth of 5. This specific concatenated system is being considered for NASA's high-speed satellite communications. The bit-error performance is evaluated by a combination of simulation and analysis. The split weight enumerators for the maximum distance separable codes are derived and used for the analysis.

In previous work, a method was presented to compute the weight distribution of a linear block code by using its trellis diagram. In this correspondence, the method is improved by using the trellis structure of linear block codes. Another method with reduced computational complexity is also proposed which uses the invariant property of a code. With these methods, the weight distributions of all extended binary primitive BCH codes of length 128 are computed, except for those for which the formulas of the weight distribution are known. It turns out that (128,64,22) extended binary primitive BCH code is formally self-dual. The probability of an undetectable error for each code is computed and its monotonicity is examined.

This article presents a suboptimum soft-decision decoding scheme for binary linear block codes based on an iterative search algorithm. The scheme uses an algebraic decoder to iteratively generate a sequence of candidate codewords one at a time using a set of test error patterns that are constructed based on the reliability information of the received symbols. When a candidate codeword is generated, it is tested based on an optimality condition. If it satisfies the optimality condition, then it is the most likely (ML) codeword and the decoding stops. If it fails the optimality test, a search for the ML codeword is conducted in a region which contains the ML codeword. The search region is determined by the current candidate codeword and the reliability of the received symbols. The search is conducted through a purged trellis diagram for the given code using the Viterbi algorithm. If the search fails to find the ML codeword, a new candidate is generated using a new test error pattern, and the optimality test and search are renewed. The process of testing and search continues until either the ML codeword is found or all the test error patterns are exhausted and the decoding process is terminated. Numerical results show that the proposed decoding scheme achieves either practically optimal performance or a performance only a fraction of a decibel away from the optimal maximum-likelihood decoding with a significant reduction in decoding complexity compared with the Viterbi decoding based on the full trellis diagram of the codes.

A method for computing the weight distribution of the third-order Reed-Muller code of length 512 is presented. Linear block codes are also examined.

This paper introduces new block coded 8-PSK modulations with unequal error protection (UEP) capabilities for Rayleigh fading channels. The design of efficient block coded modulations (BCM) over 8-PSK signal sets, for the specific purpose of UEP, over Rayleigh fading channels is considered. UEP is desirable in communications systems where part of the source information is more important, or error sensitive, such as the transmission of coded speech and data broadcasting. The proposed block modulation codes are based on the multilevel construction of Imai and Hirakawa (1977). It is shown that the use of binary linear UEP (LUEP) codes as component codes in one or two of the encoding levels provides, in addition to superior UEP capabilities, a higher error performance, at the expense of a very modest reduction in bandwidth efficiency, with respect to conventional multilevel codes. Computer simulation results show that, over a Rayleigh fading channel, a significant improvement in the coding gain is obtained by the use of binary LUEP codes as constituent codes in the multilevel construction.

The aliasing error performance of a signature register is measured by the maximum values of the aliasing error probabilities for certain ranges of the bit-error rate (and those of the test length). Based on these measures, we evaluate the performances of all the single input signature registers whose feedback polynomials are primitive polynomials of degree 16 and generator polynomials of the double-error-correcting BCH codes of the same degree. When the degree of the feedback polynomial is large, say 32, it is computationally hard to obtain the exact aliasing probability. But we observe that the numbers of codewords with large weights in the corresponding code dominate the maximum value of the aliasing probabilities. By computing the numbers of codewords of large weights, we find primitive polynomials of degree 32 whose maximum value of the aliasing probabilities is very large for some test lengths. The error performance of an LFSR with any BCH polynomial of degree m for the test length 2/sup m/2/-2 is shown to be very good by deriving the formula for the weight distribution of the corresponding code.>

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context‐free grammars, multiple context‐free grammars, and their subclasses are discussed.

An upper bound on the effective error coefficient of a two-level code with two-stage decoding is presented. This bound provides a guideline for constructing two-level codes to achieve a good trade-off between the error performance and decoding complexity. Based on this bound, good two-level decompositions of some Reed-Muller codes for two-stage decoding are found. Simulation results on the error performances of some Reed-Muller codes of lengths up to 64 with two-stage soft-decision suboptimum decoding based on their two-level decompositions are given.>

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length.>

A number of grammatical formalisms were introduced to define the syntax of natural languages. Among them are parallel multiple context-free grammars (pmcfg's) and lexical-functional grammars (lfg's). Pmcfg's and their subclass called multiple context-free grammars (mcfg's) are natural extensions of cfg's, and pmcfg's are known to be recognizable in polynomial time. Some subclasses of lfg's have been proposed, but they were shown to generate an NP-complete language. Finite state translation systems (fts') were introduced as a computational model of transformational grammars. In this paper, three subclasses of lfg's called nc-lfg's, dc-lfg's and fc-lfg's are introduced and the generative capacities of the above mentioned grammatical formalisms are investigated. First, we show that the generative capacity of fts' is equal to that of nc-lfg's. As relations among subclasses of those formalisms, it is shown that the generative capacities of deterministic fts', dc-lfg's, and pmcfg's are equal to each other, and the generative capacity of fc-lfg's is equal to that of mcfg's. It is also shown that at least one NP-complete language is generated by fts'. Consequently, deterministic fts', dc-lfg's and fc-lfg's can be recognized in polynomial time. However, fts' (and nc-lfg's) cannot, if P ≠ NP.

A method of translating natural language specifications of communication protocols into algebraic specifications is presented. Such a natural language specification specifies action sequences performed by the protocol machine (program). Usually, a sentence implicitly specifies the state of the protocol machine in which the described actions should be performed. A method of analyzing the implicitly specified states of the protocol machine is proposed, taking the OSI session protocol specification as an example. The method uses the following properties: (a) syntactic properties of a natural language; (b) syntactic properties introduced by the target algebraic specifications, e.g., subtype relations; and (c) properties of a data type, e.g., properties of timer. The results of applying this method to the main part of the OSI session protocol specification is shown.>

The aliasing error performance of signature registers is measured by the maximum values of the aliasing error probabilities for certain ranges of the bit-error rate (and those of the test length). Based on these measurements, the authors evaluate the performances of all the single input signature registers whose feedback polynomials are primitive polynomials of degree 16 and generator polynomials of the double-error-correcting BCH codes of the same degree. When the degree of the feedback polynomial is large (e.g. 32), it is computationally hard to obtain the exact value of the aliasing probability. But the authors observe that the numbers of codewords with large weights in the corresponding code determine the maximum value of the aliasing probabilities in the range 0>

It was shown earlier that for a punctured Reed-Muller (RM) code or a primitive BCH code, which contains a punctured RM code of the same minimum distance as a large subcode, the state complexity of the minimal trellis diagrams is much greater than that for an equivalent code obtained by a proper permutation of the bit positions. The problem of finding a permutation of the bit positions for a given code that minimizes the state complexity of its minimal trellis diagram is related to the generalized Hamming weight hierarchy of a code, and it is shown that, for RM codes, the standard binary order of bit positions is optimum at every bit position with respect to the state complexity of a minimal trellis diagram by using a theorem due to V.K. Wei (1991). The state complexity of the trellis diagram for the extended and permuted (64, 24) BCH code is discussed.>

An upper bound on the number of states of a minimal trellis diagram for a linear block code is derived. Using this derivation a cyclic (or shortened cyclic) code or its extended code is shown to be the worst in terms of trellis state complexity among the linear codes of the same length and dimension. The complexity of the minimal trellis diagrams for linear block codes of length 2/sup m/, including the Reed-Muller codes, is analyzed. The construction of minimal trellis diagrams for some extended and permuted primitive BCH codes is presented. It is shown that these codes have considerably simpler trellis structure than the original codes in cyclic form without bit-position permutation.>

Multistage decoding of multilevel block multilevel phase-shift keying (M-PSK) modulation codes for the additive white Gaussian noise (AWGN) channel is investigated. Several types of multistage decoding, including a suboptimum soft-decision decoding scheme, are devised and analyzed. Upper bounds on the probability of an incorrect decoding of a code are derived for the proposed multistage decoding schemes. Error probabilities of some specific multilevel block 8-PSK modulation codes are evaluated and simulated. The computation and simulation results for these codes show that with multistage decoding, significant coding gains can be achieved with large reduction in decoding complexity. In one example, it is shown that the difference in performance between the proposed suboptimum multistage soft-decision decoding and the single-stage optimum decoding is small, only a fraction of a dB loss in SNR at the block error probability of 10/sup -6/.>

A new defect-tolerant design technique for mask ROMs is proposed. In the proposed technique a Reed-Solomon code with distance three is utilized. A built-in circuit can repair a defect or defects within a word. The overhead area of the defect-tolerant circuits is estimated to be about 1% for a 4 M-bit mask ROM with eight outputs.>

The problem of distributing a Cartesian product file on multiple disks to maximize the parallelism for partial match queries is addressed. C. Faloutsos et al. (1989) have proposed an allocation method for Cartesian product files on multiple disks by using linear error-correcting codes. The performance of the allocation method is analyzed. Some conditions under which the allocation method is strictly optimal for queries with a given number of unspecified attributes are presented. A necessary and sufficient condition for a linear code to give a strictly optimal allocation method is discussed. Formulas for the average response time on queries with w unspecified attributes, denoted T/sub w/, in terms of the weight distribution of the code or its dual code, and formulas for the average response time Ton all queries, are given. Several examples whose average response times T/sub w/ or T are close to theoretical lower bounds are presented.>

The monotonic property of the probability of undetected error is considered when a shortened code of a linear code over GF(q) is used for error detection on a q-ary symmetric channel. Some conditions are presented under which the probability of undetected error is (or is not) monotonic with respect to the code length or the symbol error probability. It is shown that the probability of undetected error for a maximum distance separable code is monotonic with respect to the codelength. It is also shown that the probability of undetected error of a shortened code of any binary cyclic Hamming code generated by a trinomial is not monotonic with respect to the bit-error rate if the code length is short.>

Two important structural properties of block M(=2/sup '/)-ary PSK modulation codes, linear structure and phase symmetry, are investigated. An M-ary modulation code is first represented as a code with symbols from the integer group S/sub M-PSK/=(0,1,2,---,M-1) under modulo-M addition. Then the linear structure of block M-PSK modulation codes over S/sub M-PSK/ with respect to modulo-M vector addition is defined, and conditions are derived under which a block M-PSK modulation code is linear. Once the linear structure is developed, the phase symmetry of block M-PSK modulation codes is studied. In particular, a necessary and sufficient condition for a block M-PSK modulation code that is linear as a binary code to be invariant under 2/sup h/180 degrees /M phase rotation, for 1>

The multilevel technique for combining block coding and modulation is investigated. A general formulation is presented for multilevel modulation codes in terms of component codes with appropriate distance measures. A specific method for constructing multilevel block modulation codes with interdependency among component codes is proposed. Given a multilevel block modulation code C with no interdependency among the binary component codes, the proposed method gives a multilevel block modulation code C' that has the same rate as C, a minimum squared Euclidean distance not less than that of C, a trellis diagram with the same number of states as that of C, and a smaller number of nearest neighbor codewords than that of C. Finally, a technique is presented for analyzing the error performance of block modulation codes for an additive white Gaussian noise (AWGN) channel based on soft-decision maximum likelihood decoding. Error probabilities of some specific codes are evaluated by simulation and upper bounds based on their Euclidean weight distributions.>

A concatenated coded modulation scheme is presented for error control in data communications. The scheme is achieved by concatenating a Reed-Solomon outer code and a bandwidth efficient block inner code for M-ary phase-shift keying (PSK) modulation. Error performance of the scheme is analyzed for an additive white Gaussian noise (AWGN) channel. It is shown that extremely high reliability can be attained by using a simple M-ary PSK modulation inner-code and a 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 scheme is particularly effective for high-speed satellite communications for large file transfer where high reliability is required. A simple method is also presented for constructing block codes for M-ary PSK modulation. Soome 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. Furthermore, some of these codes are phase invariant under multiples of 45 degrees rotation.>

A robust error control coding system is presented. This system is a cascaded FEC (forward error control) scheme supported by parity retransmissions for further error correction in the erroneous data words. The error performance and throughput efficiency of the system are analyzed. Two specific examples of the error control system are studied. The first example does not use an inner code, and the outer code, which is not interleaved, is a shortened code of the NASA standard RS code over GF(2/sup 8/). The second example, as proposed for NASA uses the same shortened RS code as the base outer code C/sub 2/, except that it is interleaved to a depth of 2. It is shown that both examples provide high reliability and throughput efficiency even for high channel bit-error rates in the range of 10/sup -2/.>

Investigates the error detecting capabilities of the shortened hamming codes adopted for error detection in IEEE Standard 802.3. These codes are also used for error detection in the data link layer of the Ethernet, a local area network. The authors compute the weight distributions for various code lengths. From the results, they show the probability of undetectable error and that of detectable error for a binary symmetric channel with bit-error rate 10/sup -5/>

A coding scheme for error control in data communication systems is investigated. The scheme is obtained by cascading two error-correcting codes, called the inner and outer codes. Its error performance is analyzed for a binary symmetric channel with a bit-error rate epsilon>

In this paper, a concatenated coding scheme for error control in data communications is presented and analyzed. In this scheme, the inner code is used for both error correction and detection; however, the outer code is used only for error detection. A retransmission is requested if either the inner code decoder fails to make a successful decoding or the outer code decoder detects the presence of errors after the inner code decoding. Probability of undetected error (or decoding error) of the proposed scheme is derived. An efficient method for computing this probability is presented. Throughput efficiency of the proposed error control scheme incorporated with a selective-repeat ARQ retransmission strategy is also analyzed. Three specific examples are presented. One of the examples is proposed for error control in the NASA Telecommand System.

Recently Kasami {\em et al.} presented a linear programming approach to the weight distribution of binary linear codes [2]. Their approach to compute upper and lower bounds on the weight distribution of binary primitive BCH codes of length2^{m} - 1withm \geq 8and designed distance2t + 1with4 \leq t \leq 5is improved. From these results, the relative deviation of the number of codewords of weightj\leq 2^{m-1}from the binomial distribution2^{-mt} \left( \stackrel{2^{m}-1}{j} \right)is shown to be less than 1 percent for the following cases: (1)t = 4, j \geq 2t + 1andm \geq 16; (2)t = 4, j \geq 2t + 3and10 \leq m \leq 15; (3)t=4, j \geq 2t+5and8 \leq m \leq 9; (4)t=5,j \geq 2t+ 1andm \geq 20; (5)t=5, j \geq 2t+ 3and12 \leq m \leq 19; (6)t=5, j \geq 2t+ 5and10 \leq m \leq 11; (7)t=5, j \geq 2t + 7andm=9; (8)t= 5, j \geq 2t+ 9andm = 8.

Recently, the representative instance has been proposed as a generalized concept of the pure universal relation. Let ${\bf R} = \{ \langle R_1 ,F_1 \rangle , \cdots , \langle R_n ,F_n \rangle \}$ be a database scheme, where each $R_i $ is a set of attributes and $F_i $ is a set of functional dependencies over $R_i $. ${\bf R}$ is said to be consistent if the representative instance of every database $I = \{ r_1 , \cdots ,r_n \}$ of ${\bf R}$ satisfies $F (= F_1 \cup \cdots \cup F_n )$, that is, if whenever each relation $r_i $ satisfies its own functional dependencies $F_i $, the representative instance satisfies all the functional dependencies F. In this paper, we present the following two results, which are generalizations of the previous results by [Sag2]. (1) It can be determined in $O(n|F|\|F\|)$ time whether ${\bf R}$ is consistent, where $|F|$ is the number of functional dependencies in F and $||F||$ is the size of the description of F. (A polynomial time algorithm for determining whether ${\bf R}$ is consistent is presented, independently, in [GY].) (2) Suppose that ${\bf R}$ is consistent. Given a subset V of $R_1 \cup \cdots \cup R_n $, we can construct in $O(n|F|\|F\|)$ time a relational expression such that (a) its value is the total projection of the representative instance onto V for every database of ${\bf R}$, (b) it consists of projection, extension join, and union, and (c) it contains neither a redundant union nor a redundant join.

Shortened Hamming codes are widely used for error detection in data communications. In this paper, a method for computing the probability of an undetected error for these codes is presented. This method is then used to evaluate the error-detection performance of the shortened codes obtained from the two distance-4 Hamming codes adopted by CCITT X.25 for error control for packet-switched networks. We show that shortening a code does affect its error-detection performance.

Binary primitive BCH codes form a large class of powerful error-correcting codes. The weight distributions of primitive BCH codes are unknown except for some special classes, such as the single, double, triple error-correcting codes and some very low-rate primitive BCH codes. However, asymptotic results for the weight distribution of a large subclass of primitive BCH codes have been derived by Sidel'nikov. These results provide some insight into the weight structure of primitive BCH codes. Sidel'nikov's approach is improved and applied to the weight distribution of any binary linear block code. Then Sidel'nikov's results on the weight distributions of binary primitive BCH codes are improved and it is shown that the weights of a binary primitive code have approximate binomial distribution.

Block coding for the binary symmetric broadcast channel with two receivers is investigated. A graph-theoretic approach to the construction of a class of block codes with unequal error protection for two different sets of messages is presented. A code in this class is a direct sum of two component codes; each set of messages is encoded based on one component code. The codes in this class are easy to implement. Decoding of these codes is presented, and lower bounds on the achievable rates of these codes are derived. The bounds are tighter than the Katsman's bounds.

A distributed algorithm is presented that realizes mutual exclusion among N nodes in a computer network. The algorithm requires at most N message exchanges for one mutual exclusion invocation. Accordingly, the delay to invoke mutual exclusion is smaller than in an algorithm of Ricart and Agrawala, which requires 2*( N - 1) message exchanges per invocation. A drawback of the algorithm is that the sequence numbers contained in the messages are unbounded. It is shown that this problem can be overcome by slightly increasing the number of message exchanges.

In this paper we investigate the performance of maximum-distance-separable codes with symbols fromGF(q)when they are used for pure error detection or for simultaneous error correction and detection over aq-input andq-output discret memoryless channel with symbol error probability ε. First we show that the probability of undetected error for an MDS code used for pure error detection is upper bounded byq^{-r}and decreases monotonically as εdecreases from(q - 1)/qto 0, whereris the number of parity-check symbols of the code. Then we show that the probability of undetected error for an MDS code used for correctingtor fewer symbol errors is upper bounded byq^{-r} \Sum\min{i=0}\max{t}(\min{i} \max{n})(q - 1)^{i}and decreases monotonically as ε decreases from(q - 1)/qto 0. These results show that the MDS codes are effective for both pure error detection and simultaneous error correction and detection.

It is well known that algebraic specification methods are promising for specifying programs and for verifying their various properties formally. In this paper, an algebraic specification of information transfer procedures of high-level data link control (HDLC) procedures is presented and some of the main properties of the specification are shown. First, we introduce abstract states, state transition functions, and output functions corresponding to elementary notions extracted from the description of HDLC procedures in ISO 3309-1979 (E) and ISO 4335-1979 (E). Second, we show axioms which represent the relations between the values of functions before and after the state transitions. Then, it is proved that the specification is ``consistent,'' ``sufficiently complete,'' and ``nonredundant.'' Also it is shown that an implementation which realizes the specification is naturally derived. In the last section, verification of various properties of HDLC procedures is formulated in the same framework as the algebraic specification, and some verification examples are presented.

The probability of undetected error of linear block codes for use on a binary symmetric channel is investigated. Upper hounds are derived. Several classes of linear block codes are proved to have good error-detecting capability.

We relate coding for the two-user multiple-access binary adder channel to a problem in graph theory, known as the independent set problem. Graph-theoretic approaches to coding for both synchronized and nonsynchronized two-user adder channels are presented. Using the Tuŕan theorem on the independence number of a simple graph, we are able to improve the lower bounds on the achievable rates of uniquely and\delta-decodable codes for the synchronized adder channel derived by Kasami and Lin. We are also able to derive lower bounds on the achievable rates of uniquely decodable codes for the nonsynchronized adder channel. We show that the rates of Deaett-Wolf codes for the nonsynchronized adder channel fall below the bounds. Synchronizing sequences for the nonsynchronized adder channel are constructed.

Two decision problems related to multivalued dependencies in a relational database are considered. In this paper, an algorithm is presented for deciding whether or not a multivalued dependency can be derived from sets F of functional dependencies and M of multivalued dependencies on a set U of attributes, whose running time is proportional to min $(k^2 |U|,||F \cup M||^2 )$ where k and $|U|$ are the numbers of dependencies in $F \cup M$ and attributes in U, respectively, and $||F \cup M||$ is the size of description of F and M. A related algorithm is also considered which decides whether or not there exists a nontrivial multivalued dependency that is valid in a projection of the original relation.

Block coding for a memoryless two-input single-output multiple-access channel, called a two-user adder channel, is studied. Techniques for constructing codes for this particular channel are presented. Upper and lower bounds on the achievable rates of these codes are derived. These bounds define various two-dimensional regions for the achievable rates of codes for the two-user adder channel.

A scheme is presented for decoding linear\delta-decodable codes for the two-user noisy adder channel that exploits the linearity of the codes and corrects all patterns of\lfloor (\delta - 1)/2 \rflooror fewer transmission errors.

A scheme for storing information in a memory system with defective memory ceils using "additive" codes was proposed by Kuznetsov and Tsybakov. When a source message is to be stored in a memory with defective cells, a code vectorxmasking the defect pattern of the memory is formed by adding a vector defined by the message and the defect pattern to the encoded message, and thenxis stored. The decoding process does not require the defect information. Considerably better bounds on the information rate of codes of this type which are capable of masking multiple defects and correcting multiple temporary errors are presented. The difference between the upper and lower bounds approaches the difference between the known best upper and lower bounds for random error correcting linear codes as the word length becomes large. Examples of efficient codes for masking double or fewer defects and correcting multiple temporary errors are presented.

In this paper, coding for a multiple-access discrete memoryless channel is investigated. Block codes which are uniquely decodable and capable of correcting errors are constructed.

It is shown that there exist arbitrarily long quasi-cyclic(2k,k)binary codes that meet a bound slightly weaker than the Gilbert-Varshamov bound. This is a refinement of the result of Chen, Peterson, and Weldon [1].

A construction of cyclic codes in which an "inner" cyclic code is concatenated with appropriately chosen "outer" cyclic codes is presented. An example of the construction that improves on BCH codes of low rate is provided. Conversely, any cyclic code of lengthn_1 n_2can be constructed by this construction, wheren_1andn_2are relatively prime.

A negative gate is a gate that can realize an arbitrary negative function (or monotone decreasing function) and a positive gate is one that can realize an arbitrary positive function (or monotone increasing function). This paper discusses methods of realizing a given logical function or a given set of logical functions using a minimum number of negative gates alone or using a minimum number of negative and positive gates.

For1 \leq i \leq m - s- 2and0 \leq s \leq m -2i, the intersection of the binary BCH code of designed distance2 ^{m-s-1} - 2 ^{m-s-t-1} - 1and length2^m - 1with the shortened(s + 2)th-order Reed-Muller code of length2^m -- 1has codewords of weight2^{m-s-1} - 2^{m-s-t-1} - 1.

The basic properties and realization of failsafe combinational logic nets and failsafe sequential machines are discussed. The present note concerns totally asymmetric faiiure nets which are composed only of (+) elements and/ or (-) elements, where a (+) element is an asymmetric failure element which never fails to logical zero and a (-) element is defined similarly.

The class of polynomial codes introduced by Kasami et al. has considerable inherent algebraic and geometric structure. It has been shown that this class of codes and their dual codes contain many important classes of cyclic codes as subclasses, such as BCH codes, Reed-Solomon codes, generalized Reed-Muller codes, projective geometry codes, and Euclidean geometry codes. The purpose of this paper is to investigate further properties of polynomial codes and their duals. First, majority-logic decoding for the duals of certain primitive polynomial codes is considered. Two methods of forming nonorthogonal parity-check sums are presented. Second, the maximality of Euclidean geometry codes is proved. The roots of the generator polynomial of an Euclidean geometry code are specified.

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.

The following theorem is proved. Letf(x_1,\cdots, x_m)be a binary nonzero polynomial ofmvariables of degree\nu. H the number of binarym-tuples(a_1,\cdots, a_m)withf(a_1, \cdots, a_m)= 1 is less than2^{m-\nu+1}, thenfcan be reduced by an invertible affme transformation of its variables to one of the following forms. \begin{equation} f = y_1 \cdots y_{\nu - \mu} (y_{\nu-\mu+1} \cdots y_{\nu} + y_{\nu+1} \cdots y_{\nu+\mu}), \end{equation} wherem \geq \nu+\muand\nu \geq \mu \geq 3. \begin{equation} f = y_1 \cdots y_{\nu-2}(y_{\nu-1} y_{\nu} + y_{\nu+1} y_{\nu+2} + \cdots + y_{\nu+2\mu -3} y_{\nu+2\mu-2}), \end{equation} This theorem completely characterizes the codewords of the\nuth-order Reed-Muller code whose weights are less than twice the minimum weight and leads to the weight enumerators for those codewords. These weight formulas are extensions of Berlekamp and Sloane's results.

A syntax-analysis Mgorithm is presented for a language generated by an unambiguous context-free grammar in a number of elementary operations proportional to n = log n, where n is the length of a given string, using a random access memory.The amount of memory required for the algorithm is proportional to n 2 log n.The proposed algorithm is a modified version of Cocke's algorithm and utilizes a eertair, property of unambiguous normal grammars.

An upper bound on the transmission ratiok/nfor binary cyclic codes whose extended codes are invariant under the affine group of permutations, is presented. As a consequence, the transmission ratiok/nof any affine-invariant code with a fixedd(minimum weight)/nis shown to approach zero as the code length n increases. This is an extension of the Lin and Weldon result for primitive BCH codes.

It is shown that ifm \neq 8, 12andm > 6, there are some binary primitive BCH codes (BCH codes in a narrow sense) of length2^{m} - 1whose minimum weight is greater than the BCH bound. This gives a negative answer to the question posed by Peterson [1] of whether or not the BCH bound is always the actual minimum weight of a binary primitive BCH code. It is also shown that for any evenm \geq 6, there are some binary cyclic codes of length2^{m} - 1that have more information digits than the primitive BCH codes of length2^{m} - 1with the same minimum weight.

Many data-transmission and data-storage systems are corrupted by disturbances of both the burst type and the random type. In this paper two classes of error-correcting codes for use with these systems have been constructed analytically and with the aid of a computer. Although not optimal, these codes do have the advantage of ease of implementation,

An extension of Goethals' results [3] is presented. Cyclic codes of composite block lengthn = n_{1}n_{2}withn_{1}andn_{2}relatively prime are considered. By using a modified form of the Mattson-Solomon formulation [5], some lower bounds on the minimum weight are obtained. These lower bounds improve on the BCH bound [4] for a considerable number of nonprimitive BCH codes.

First it is shown that all binary Reed-Muller codes with one digit dropped can be made cyclic by rearranging the digits. Then a natural generalization to the nonbinary case is presented, which also includes the Reed-Muller codes and Reed-Solomon codes as special cases. The generator polynomial is characterized and the minimum weight is established. Finally, some results on weight distribution are given.

A class of cyclic codes is introduced by a polynomial approach that is an extension of the Mattson-Solomon method and of the Muller method. This class of codes contains several important classes of codes as subclasses, namely, BCH codes, Reed-Solomon codes, generalized primitive Reed-Muller codes, and finite geometry codes. Certain fundamental properties of this class of codes are derived. Some subclasses are shown to be majority-logic decodable.

This paper presents a systematic procedure for finding optimum error-correcting group codes for the binary symmetric channel with m check digits and a minimum distance not less than do, where m and do are given integers. Some new schemes for reducing the computing time are used. The search procedure is readily programmable for computer execution and several programs were carried out on an IBM 7044. The newly found seven optimum triple-error-correcting group codes and six optimum double-error-correcting group codes including five quasi-perfect double-error-correcting codes are tabulated. Also, a list of optimum shortened cyclic codes found by a similar procedure is presented. The efficiency of the search procedure is demonstrated by the fact that the program yielded the new codes in a fairly short time.

A decoding procedure for multiple-error-correcting cyclic codes is described. This method is very simple in principle and the mechanization is easy for short codes with relatively high redundancy. Applications are made to the cyclic Golay code, the Bose-Chaudhuri(63, 45), (31, 16), (31, 11)codes and the(41, 21)cyclic codes. A block diagram for a decoder for the Golay code is shown.

This paper is concerned with the construction of the most efficient shortened cyclic (pseudo-cyclic) codes that can correct every burst-error of lengthbor less. These codes have the maximum number of information digitskamong all shortened cyclic burst-bcodes with a given number of check digitsr. The search procedure described is readily programmable for computer execution and efficient particularly for the case whereris close to the theoretical minimum of2bcheck digits. For2 \leq b \leq 10, several optimum shortened cyclic codes in the above-mentioned sense have been found. Their code-lengths and generators are tabulated in this paper.

This paper deals with the linear estimation of noise corrupted signal waveforms, from observation over a specified finite time-interval. Two new features are delineated in this paper: 1) the estimating operator is assumed to be finite-dimensional, because economically realizable operators are finite-dimensional in general, and 2) the cost of observation and estimation is taken into account, and assumed to be dependent upon the dimension of the operator only. As a result, the optimum linear finite-dimensional operator that minimizes the risk (the sum of cost and average loss) is obtained for the case in which a quadratic loss function due to error is adopted.