In this paper, we propose a zero-forcing (ZF) Tomlinson-Harashima precoding (THP) with substream permutations based on the bit rate maximization for single-user MIMO (SU-MIMO) systems. We study the effect of substream permutations on the ZF-THP SU-MIMO systems, when the mean squared error (MSE) and the bit rate are adopted for the selection of the permutation matrix as criteria. Based on our analysis, we propose a method to increase the bit rate by substream permutations, and derive QR and Cholesky decomposition-based algorithms which realize the proposed method. Furthermore, to improve the error rate performance, we apply zero transmission to subchannels with low signal-to-noise ratios. Numerical examples are provided to demonstrate the effectiveness of the proposed THP MIMO system.

Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure πDDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.

The complete subtree (CS) method is widely accepted for the broadcast encryption. A new method for assigning keys in the CS method is proposed in this paper. The essential idea behind the proposed method is to use two trapdoor permutations. Using the trapdoor information, the key management center computes and assigns a key to each terminal so that the terminal can derive all information necessary in the CS method. A terminal has to keep just one key, while log2 N + 1 keys were needed in the original CS method where N is the number of all terminals. The permutations to be used need to satisfy a certain property which is similar to but slightly different from the claw-free property. The needed property, named strongly semi-claw-free property, is formalized in terms of probabilistic polynomial time algorithm, and its relation to the claw-free property is discussed. It is also shown that if the used permutations fulfill the strongly semi-claw-free property, then the proposed method is secure against attacks of malicious users.

The complete subtree (CS) method is one of the most well-known broadcast encryptions which do not enforce the receivers to keep "online." This paper is to reduce the size of secret information which must be stored in a terminal of the method. In the original CS method, the size of the secret information increases as the number of terminals increases. It is shown in this paper that, by making use of a one-way trapdoor permutation, we can make the size constant regardless of the number of terminals. The security of the proposed scheme is investigated, and detailed comparison with other similar schemes is presented. The proposed scheme is suitable for practical implementations of the CS method.

A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.

A family C of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer n>0, a family C of permutations on [n]={1,2,. . . ,n} is said to be min-wise independent if for any (nonempty) X [n] and any x X, Pr ( min {π(X)} = π(x))= ||X||-1 when π is chosen uniformly at random from C, where ||A|| is the cardinality of a finite set A. For any integer n>0, it has been known that (1) ||C|| lcm(n,n-1,. . . ,2,1) = en-o(n) for any family C of min-wise independent permutations on [n]; (2) there exists a polynomial time samplable C family of min-wise independent permutations on [n] such that ||C|| 4n. However, it has been unclear whether there exists a min-wise independent family C such that ||C|| = lcm(n,n-1,. . . ,2,1) for each integer n>0 and how to construct such a family C of min-wise independent permutations for each integer n>0 if it exists. In this paper, we shall construct a family Fn of permutations for each integer n>0 and show that Fn is min-wise independent and ||Fn|| = lcm(n,n-1,. . . ,2,1). Moreover, we present a polynomial time sampling algorithm for the family. Thus the family Fn of min-wise independent permutations is optimal in the sense of family size and is easy to implement because of its polynomial time samplability.

Recently reported multidimensional geometrically uniform signal constellations (L MPSK and Decomposed-Lattice constellations) are joined in the term of Generalized Permutation Alphabets (GPA). Possibility of a binary isometric labeling of GPA's is completely characterized. An algorithm for constructing generating groups of PSK-type GPA is proposed. We show that this concept, when is extended to the lattice, gives rise to a class of new coset codes which perform out best codes listed in [11].

For L 2, M 8, and transmission rate R = (log2M-1) bit/sym, a method for constructing GU trellis codes with L MPSK constellations is proposed and it is shown that the maximally achievable free distance is twice larger than it was previously reported for GU codes. Basides being geometrically uniform, these codes perform as good as Pietrobon's non-GU trellis codes with multidimensional MPSK constellations.

Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show that (1) if oneway permutations exist, then there exists a language L that has a checker but does not have a self-corrector. We then introduce a novel notion of "self-improvers" that trans form a faulty program into a less faulty program, and show that (2) if a function f has a self-tester/corrector pair, then f has a self-improver. As the applications of self-improvers, we finally show that (3) if a function f has a self-tester/corrector pair, then f has a flexible self-tester and (4) if a function f has a self-tester/corrector pair, then f has self-improver that transforms a faulty program into an alomost correct program.

Damgrd defined the notion of a collision intractable hash functions and showed that there exists a collection of collision intractable hash functions if there exists a collection of claw-free permutation pairs. For a long time, the necessary and sufficient condition for the existence of a collection of collision intractable hash functions has not been known, however, very recently Russell finally showed that there exists a collection of collision intractable hash functions iff there exists a collection of claw-free pseudo-permutation pairs. In this paper, we show an alternative necessary and sufficient condition for the existence of a collection of collision intractable hash functions, i.e., there exists a collection of collision intractable hash functions iff there exists a collection of distinction intractable pseudo-permutations.

In this paper we estimate the number of permutations realizable in fault-tolerant multistage interconnection networks designed to tolerate faults on any switching element. The Parallel Omega network and the INDRA network are representative types of fault-tolerate multistage interconnection networks designed to tolerate a single fault. In order to evaluate the enhancement in the function of network by preparing the hardware redundancy for fault-tolerance, we estimate the number of permutations realizable in fault-tolerant networks. This result enables us to set up a standard to evaluate the hardware redundancy required to tolerate multifaults from the viewpoint of the enhancement of network function. This paper concludes that in the case where the number of inputs is up to 32 the increase ratio of the number of realizable permutations is no more than 1/0.73 even if the tolerance to multifaults is prepared instead of the tolerance to a single fault.