2251486
Euclidean and Hermitian self-dual MDS codes over large finite fields
The first author constructed new extremal binary self-dual codes (IEEE Trans. Inform. Theory 47 (2001) 386-393) and new self-dual codes over GF(4) with the highest known minimum weights (IEEE Trans. Inform. Theory 47 (2001) 1575-1580). The method used was to build self-dual codes from a given self-dual code of a smaller length. In this paper, we develop a complete generalization of this method for the Euclidean and Hermitian self-dual codes over finite fields GF(q). Using this method we construct many Euclidean and Hermitian self-dual MDS (or near MDS) codes of length up to 12 over various finite fields GF(q), where q = 8, 9, 16, 25, 32, 41, 49, 53, 64, 81, and 128. Our results on the minimum weights of (near) MDS self-dual codes over large fields give a better bound than the Pless-Pierce bound obtained from a modified Gilbert-Varshamov bound.
3197241
Explicit construction of families of LDPC codes with no 4-cycles
Low-density parity-check (LDPC) codes are serious contenders to turbo codes in terms of decoding performance. One of the main problems is to give an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and m/spl ges/2, Lazebnik and Ustimenko construct a q-regular bipartite graph D(m,q) on 2q/sup m/ vertices, which has girth at least 2/spl lceil/m/2/spl rceil/+4. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine the dimension and minimum weight of LU(2,q), and show that the weight of its minimum stopping set is at least q+2 for q odd and exactly q+2 for q even. We know that D(2,q) has girth 6 and diameter 4, whereas D(3,q) has girth 8 and diameter 6. We prove that for an odd prime p, LU(3,p) is a [p/sup 3/,k] code with k/spl ges/(p/sup 3/-2p/sup 2/+3p-2)/2. We show that the minimum weight and the weight of the minimum stopping set of LU(3,q) are at least 2q and they are exactly 2q for many LU(3,q) codes. We find some interesting LDPC codes by our partial row construction. We also give simulation results for some of our codes.
14157019
Projections of Binary Linear Codes onto Larger Fields
We study certain projections of binary linear codes onto larger fields. These projections include the well-known projection of the extended Golay [24,12,8] code onto the hexacode over $\mbox{GF}(4)$ and the projection of the Reed--Muller code R(2,5) onto the unique self-dual [8,4,4] code over $\mbox{GF}(4)$. We give a characterization of these projections, and we construct several binary linear codes which have best known optimal parameters, for instance, [20,11,5], [40,22,8], [48,21,12], and [72,31,16]. We also relate the automorphism group of a quaternary code to that of the corresponding binary code.
16103417
Designs in Additive Codes over GF(4)
The purpose of this paper is to study designs in additive codes over GF(4). There are two types of designs. One is a classical t-design with repeated blocks. In this case we have an analog of the Assmus–Mattson Theorem for additive codes over GF(4). The other is a generalized t-design first introduced by Delsarte [4]. As an example, we consider the dodecacode, which is the unique additive even self-dual (12, 212, 6) code. We show that there exists a 5-(12, 6, 3) design in the dodecacode with either 3 distinct blocks or 3 repeated blocks covering a 5-set. We also find a new simple 3-(11, 5, 4) design in the shortened dodecacode by a computer search. Additionally we show that any extremal additive even self-dual code over GF(4) is homogeneous.
15382159
Hybrid recursive energy-based method for robust optical flow on large motion fields
We present a new reliable hybrid recursive method for optical flow estimation. The method efficiently combines the advantage of discrete motion estimation and optical flow estimation in a recursive block-to-pixel estimation scheme. Integrated local and global approaches using the robust statistic of anisotropic diffusion remove outliers from the estimated motion field. We separately describe the process with two frameworks i.e. an incremental updating framework and a robust energy minimization framework. With robust error norms of Perona and Marik anisotropic diffusion, the formulation usually leads to non-convex optimization problems. Thus, the solution has many local minima, and convergence to the global minima is not guaranteed. Our hybrid recursive energy-based method employs a hierarchical block-to-pixel estimation concept to prevent this problem. The experimental results prove the excellent performance on several large motion fields.
9661446
Normalization for neural network in genetic search
Jung-Hwan Kim School of Computer Science and Engineering Seoul National University Shilim-dong, Kwanak-gu, Seoul, 151-742 Korea aram@soar.snu.ac.kr Sung-Soon Choi School of Computer Science and Engineering Seoul National University Shilim-dong, Kwanak-gu, Seoul, 151-742 Korea sschoi@soar.snu.ac.kr Byung-Ro Moon School of Computer Science and Engineering Seoul National University Shilim-dong, Kwanak-gu, Seoul, 151-742 Korea moon@soar.snu.ac.kr
14570877
Genetic Elevator Group Control
In a tall building with multiple elevators, it is a notoriously di cult task to control the elevators in the most e cient manner [1].The system proposed in this paper contains two key ideas. First, it continuously generates dispatch functions by adaptation to changes in passenger tra c. Second, it tries to reduce passengers' waiting time by multiple elevator allocation when it is expected that one elevator cannot serve all the passengers for a hall call at a oor.
15935373
Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs
Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set of pairs of matchings must each produce Hamilton cycles (with suitable restrictions on the prescribed set of pairs). We also show how the result with four matchings implies that a random d-regular graph for fixed even d?4 asymptotically almost surely decomposes into d/2 Hamilton cycles. This completes a general result on the edge-decomposition of a random regular graph into regular spanning subgraphs of given degrees together with Hamilton cycles and verifies conjectures of Janson and of Robinson and Wormald.
1994375
Effective Temporal Aggregation Using Point-Based Trees
Temporal databases introduce the concept of time into underlying data, and provide built-in facilities that allow users to store and retrieve time-varying data. The aggregation in temporal databases, that is, temporal aggregation is an extension of conventional aggregation on the domain and range of aggregates to include time concept. Temporal aggregation is important for various applications, but is very expensive. In this paper, we propose a new tree structure for temporal aggregation, called PA-tree, and aggregate processing method based on the PA-tree. We show that the time complexity of the proposed method is better than those of the existing methods. The time complexity of the proposed method is shown to be indeed the lower bound of the problem. We perform comparative experiments and show the performance advantage of our proposed method in practice.