This correspondence revisits the idea of constructing a binary [mn,mk] code from an [n,k] code over F/sub 2//sup m/ by concatenating the code with a suitable basis representation of F/sub 2//sup m/ over F/sub 2/. We construct two nonequivalent examples of doubly even self-dual binary codes of length 160 which turn out to be of minimum distance 24. This improves the lower bound for this class of codes, whereas the upper bound is given by 28. The construction at hand seems to be of interest beyond this particular example.

The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.

In this article, the computation of the entropy rate H(y) of a binary-valued stochastic process (Y/sub 1/, Y/sub 2/,...) which is a function of a stationary, time-invariant and irreducible Markov chain (X/sub 1/, X/sub 2/,..) is considered. The central idea of this article is to replace the summation over all words of length n by a summation over a complete set of prefixes (or prefixset for brevity). A prefixset W is a finite set of words (not necessarily of equal length) containing a unique prefix for each word of sufficient length. The method of prefixsets is of interest beyond computing the entropy rate. For the problem of estimating the next state of a Markov chain from observed output sequences, we can precompute a prefixset W of these sequences and associate a unique estimate of the state with each of the elements of W. The method also has a strong relation with variable-to-fixed length (Tunstall) codes. It replaces the set of all words of a given length by a prefixset of "more typical" words, effectively balancing the contributions of all words in the bounds.

The famous max-flow min-cut theorem states that a source node s can send information through a network (V,E) to a sink node t at a data rate determined by the min-cut separating s and t. Recently it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to reencode the information they receive. In contrast, we present graphs where without coding the rate must be a factor Ω(log|V|) smaller. However, so far no fast algorithms for constructing appropriate coding schemes were known. Our main result are polynomial time algorithms for constructing coding schemes for multicasting at the maximal data rate.

In a parallel concatenated convolutional code, an information sequence is encoded by a convolutional encoder, and an interleaved version of the information sequence is encoded by another convolutional encoder. We discuss the situation in which we require both convolutional encoders to end in the all-zero state. To do so, we have to split an information word in two parts. One part contains the true information bits, and the second part contains the so-called tail bits, which are special bits with values computed such that both encoders end in the all-zero state. Depending on the interleaver, a different number of tail bits are needed. By using a constructive method, we give a characterization of all interleavers for a prescribed number of tail bits. We explain the method of encoding. In addition, simulations have been carried out to investigate the performance of codes resulting from simultaneous zero-tailing. This shows that simultaneous zero-tailing is similar in performance as compared to previously known zero-tailing methods (but with fewer trellis termination bits) and that it is better than zero-tailing just one of the encoders.

Abstract Physical puzzles that can be solved with methods for permutation groups are considered and classified according to a number of abstract properties. The approach for solution is based on word stabilizer chains (the transversal elements are factored in words in a given list of generators). New methods are presented to construct word stabilizer chains that take advantage of the special structures present in physical puzzles. In many cases the methods are successful in avoiding the exponential growth of word length that plagues stabilizer chain methods to construct transversal elements. Finally, a classification scheme for puzzles is presented which helps with finding the permutation group related to the puzzle. 1 Introduction It is a well known fact that Rubik's Cube can be solved with algorithms for permutation groups. But how do you do this efficiently? In fact, it is essential to produce a solution with as few moves as possible. This paper focuses on puzzles where permutation group methods contribute substantially to their solution. In some cases the puzzle has to be looked at in the right way to see the group in it. The puzzles are solved with new methods to construct and use stabilizer chains containing words in the generators as transversal elements. In particular: ffl A heuristic method for choosing a good base. ffl Optimized procedures to create stabilizer chains containing short words (based on ideas of Minkwitz [13]).

The problem of decomposing a single permutation into a conjugated tensor product of smaller permutations is solved.Iu general, the decomposition is not uniquely determined.An algorithm is presented which enumerates all solutions.In particular, it is possible to decide considerably fast if a permutation is tensor-indecomposable. ANNEXSTEIN, F., AND BAUMSLAG, M.A unified approach to off-line permutation routing on parallel networks.