The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] linear code(56hit)

41-56hit(56hit)

  • An Application of Linear Codes to the Problem of Source Coding with Partial Side Information

    Shigeaki KUZUOKA  

     
    PAPER-Information Theory

      Vol:
    E91-A No:8
      Page(s):
    2151-2158

    This paper clarifies the adequacy of the linear channel coding approach for the source coding with partial side information at the decoder. A sufficient condition for an ensemble of linear codes which achieves the Wyner's bound is given. Our result reveals that, by combining a good lossy code, an LDPC code ensemble gives a good code for source coding with partial side information at the decoder.

  • Secret Key Agreement from Correlated Source Outputs Using Low Density Parity Check Matrices

    Jun MURAMATSU  

     
    PAPER-Information Theory

      Vol:
    E89-A No:7
      Page(s):
    2036-2046

    This paper deals with a secret key agreement problem from correlated random numbers. It is proved that there is a pair of linear matrices that yields a secret key agreement in the situation wherein a sender, a legitimate receiver, and an eavesdropper have access to correlated random numbers. A relation between the coding problem of correlated sources and a secret key agreement problem from correlated random numbers are also discussed.

  • A Note on Construction of Orthogonal Arrays with Unequal Strength from Error-Correcting Codes

    Tomohiko SAITO  Toshiyasu MATSUSHIMA  Shigeichi HIRASAWA  

     
    PAPER

      Vol:
    E89-A No:5
      Page(s):
    1307-1315

    Orthogonal Arrays (OAs) have been playing important roles in the field of experimental design. It has been known that OAs are closely related to error-correcting codes. Therefore, many OAs can be constructed from error-correcting codes. But these OAs are suitable for only cases that equal interaction effects can be assumed, for example, all two-factor interaction effects. Since these cases are rare in experimental design, we cannot say that OAs from error-correcting codes are practical. In this paper, we define OAs with unequal strength. In terms of our terminology, OAs from error-correcting codes are OAs with equal strength. We show that OAs with unequal strength are closer to practical OAs than OAs with equal strength. And we clarify the relation between OAs with unequal strength and unequal error-correcting codes. Finally, we propose some construction methods of OAs with unequal strength from unequal error-correcting codes.

  • Simulated Random Coding Algorithm for Correlated Sources with Ensemble of Linear Matrices

    Jun MURAMATSU  Takafumi MUKOUCHI  

     
    LETTER-Information Theory

      Vol:
    E88-A No:9
      Page(s):
    2475-2480

    The explicit construction of a universal source code for correlated sources is presented. The construction is based on a technique of simulated random coding algorithms [5]. The proposed algorithm simulates the random generation of linear codes. For every pair of correlated sources whose achievable rate region includes a given pair of encoding rates, the decoding error rate of the proposed algorithm goes to zero almost surely as the block length goes to infinity.

  • On Probabilistic Scheme for Encryption Using Nonlinear Codes Mapped from 4 Linear Codes

    Chunming RONG  

     
    LETTER

      Vol:
    E86-A No:9
      Page(s):
    2248-2250

    Probabilistic encryption becomes more and more important since its ability to against chosen-ciphertext attack. Applications like online voting schemes and one-show credentials are based on probabilistic encryption. Research on good probabilistic encryptions are on going, while many good deterministic encryption schemes are already well implemented and available in many systems. To convert any deterministic encryption scheme into a probabilistic encryption scheme, a randomized media is needed to apply on the message and carry the message over as an randomized input. In this paper, nonlinear codes obtained by certain mapping from linear error-correcting codes are considered to serve as such carrying media. Binary nonlinear codes obtained by Gray mapping from 4-linear codes are discussed as example for a such scheme.

  • An Algorithm for Augmenting a Binary Linear Code up to Gilbert Bound and New Codes Obtained by the Algorithm

    Tadashi WADAYAMA  Hiroyuki KADOKAWA  

     
    PAPER-Coding Theory

      Vol:
    E85-A No:10
      Page(s):
    2196-2202

    An algorithm for augmenting a binary linear code is presented. The input to the code augmenting algorithm is (n,k,d) code C and the output is an (n,k*,d) augmented code C (k* k) satisfying C C and the Gilbert bound. The algorithm can be considered as an efficient implementation of the proof of Gilbert bound; for a given binary linear code C, the algorithm first finds a coset leader with the largest weight. If the weight of the coset leader is greater than or equal to the minimum distance of C, the coset leader is included to the basis of C.

  • All-or-Nothing Transform Based on a Linear Code

    Hidenori KUWAKADO  Hatsukazu TANAKA  

     
    LETTER

      Vol:
    E85-A No:5
      Page(s):
    1084-1087

    An all-or-nothing transform (AONT), which has been proposed by Rivest, is one of encryption modes. The AONT is intended to increase the cost of brute-fore attacks on a block cipher. This paper provides the revised definition of an unconditionally secure AONT, and shows the instance of an optimal unconditionally secure AONT. In addition, we propose a computationally secure AONT such that any information on a message cannot be obtained regardless of the position of the lost block due to a linear code.

  • A Search Algorithm for Bases of Calderbank-Shor-Steane Type Quantum Error-Correcting Codes

    Kin-ichiroh TOKIWA  Hatsukazu TANAKA  

     
    PAPER-Coding Theory

      Vol:
    E84-A No:3
      Page(s):
    860-865

    Recently, Vatan, Roychowdhury and Anantram have presented two types of revised versions of the Calderbank-Shor-Steane code construction, and have also provided an exhaustive procedure for determining bases of quantum error-correcting codes. In this paper, we investigate the revised versions given by Vatan et al., and point out that there is no essential difference between them. In addition, we propose an efficient algorithm for searching for bases of quantum error-correcting codes. The proposed algorithm is based on some fundamental properties of classical linear codes, and has much lower complexity than Vatan et al.'s procedure.

  • Approximating the Maximum Weight of Linear Codes is APX-Complete

    Toshiya ITOH  

     
    PAPER

      Vol:
    E83-A No:4
      Page(s):
    606-613

    The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical importance and of theoretical interest. These problems are known to be NP-hard to approximate within any constant relative error to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generator matrix of a linear code C, find a codeword c C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT PTAS unless P=NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHT to make the approximation upper and lower bounds more precise, and show that (1) MAX-WEIGHT is APX-complete; (2) MAX-WEIGHT is approximable within relative error 1/2 to the optimum; (3) MAX-WEIGHT is not approximable within relative error 1/10 to the optimum unless P=NP.

  • A Sufficient Condition for Ruling Out Some Useless Test Error Patterns in Iterative Decoding Algorithms

    Takuya KOUMOTO  Tadao KASAMI  Shu LIN  

     
    PAPER-Information Theory and Coding Theory

      Vol:
    E81-A No:2
      Page(s):
    321-326

    In an iterative decoding algorithm, such as Chase Type-II decoding algorithm and its improvements, candidate codewords for a received vector are generated for test based on a bounded-distance decoder and a set of test error patterns. It is desirable to remove useless test error patterns in these decoding algorithms. This paper presents a sufficient condition for ruling out some useless test error patterns. If this condition holds for a test error patterns e, then e can not produce a candidate codeword with a correlation metric larger than those of the candidate codewords generated already and hence e is useless. This significantly reduces the decoding operations in Chase type-II decoding algorithm or decoding iterations in its improvements.

  • Low Weight Subtrellises for Binary Linear Block Codes and Their Applications

    Tadao KASAMI  Takuya KOUMOTO  Toru FUJIWARA  Hiroshi YAMAMOTO  Yoshihisa DESAKI  Shu LIN  

     
    PAPER-Coding Theory

      Vol:
    E80-A No:11
      Page(s):
    2095-2103

    Subtrellises for low-weight codewords of binary linear block codes have been recently used in a number of trellis-based decoding algorithms to achieve near-optimum or suboptimum error performance with a significant reduction in decoding complexity. An algorithm for purging a full code trellis to obtain a low-weight subtrellis has been proposed by H.T. Moorthy et al. This algorithm is effective for codes of short to medium lengths, however for long codes, it becomes very time consuming. This paper investigates the structure and complexity of low-weight subtrellises for binary linear block codes. A construction method for these subtrellises is presented. The state and branch complexities of low-weight subtrellises for Reed-Muller codes and some extended BCH codes are given. In addition, a recursive algorithm for searching the most likely codeword in low-weight subtrellis-based decoding algorithm is proposed. This recursive algorithm is more efficient than the conventional Viterbi algorithm.

  • Fault-Tolerant Graphs for Hypercubes and Tori*

    Toshinori YAMADA  Koji YAMAMOTO  Shuichi UENO  

     
    PAPER-Fault Diagnosis/Tolerance

      Vol:
    E79-D No:8
      Page(s):
    1147-1152

    Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number Δ(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate Δ(t, H) for the hypercube and torus, which are well-known as important interconnection networks for multiprocessor systems. If we denote the hypercube and the square torus on N vertices by QN and DN respectively, we show, among others, that Δ(t, QN) = O(tN log(log N/t + log 2e)) for any t and N (t 2), and Δ(1, DN) = N/2 for N even.

  • A Bound on Uniquely Decodable Code Pair for Two-User Binary Adder Channel

    Jian-Jun SHI  Yoichiro WATANABE  

     
    PAPER-Information Theory and Coding Theory

      Vol:
    E79-A No:5
      Page(s):
    687-693

    A uniquely decodable code pair (C, S) is considered for the two-user binary adder channel. When the first code C is linear, a lower bound of |S| is formulated and a uniquely decodable code pair (C, S) is presented. When a rate R1 of C is less than 1/3, a rate R2of S is greater than the best rate known previously.

  • Decoder Error Probability of Binary Linear Block Codes and Its Application to Binary Primitive BCH Codes

    Min-Goo KIM  Jae Hong LEE  

     
    PAPER-Information Theory and Coding Theory

      Vol:
    E79-A No:4
      Page(s):
    592-599

    McEliece and Swanson offerred an upper bound on the decorder error probability of Reed-Solomon codes. In this paper, we investigate the decorder error probability of binary linear block codes and verify its properties, and apply it to binary primitive BCH codes. It is shown that the decorder error probability of an (n,k,t) binary linear block code is determined by PE uniquely if it is a constant. We derive the decorder error probability of (n,k,t) binary primitive BCH codes with n=2m-1 and +1 and show that the decorder error probabilities of those codes are close to PE if codelengh is large and coderate is high. We also compute and analyze the decorder error probabilities of some binary primitive BCH codes.

  • Uniquely Decodable Code for Three-User Binary Adder Channel

    Jian-Jun SHI  Yoichiro WATANABE  

     
    LETTER

      Vol:
    E78-A No:9
      Page(s):
    1206-1208

    A uniquely decodable code (C1, C2, C3) is investigated for the three-user binary adder channel. The uniquely decodable code is constructed as follows: If C1 is an (n, k) linear code with a generator matrix, C2 is a coset of C1 and C3 is a set of all coset leaders, then the code (C1, C2, C3) is uniquely decodable and its total rate is equal to 1k/n, n2k. This code is easily decodable.

  • On Structural Complexity of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes

    Tadao KASAMI  Toyoo TAKATA  Toru FUJIWARA  Shu LIN  

     
    PAPER

      Vol:
    E76-A No:9
      Page(s):
    1411-1421

    A linear block code has a finite-length trellis diagram which terminates at the length of the code. Such a trellis diagram is expressed and constructed in terms of sections. The complexity of an L-section trellis diagram for a linear block code is measured by the state and branch complexities, the state connectivity, and the parallel structure. The state complexity is defined as the number of states at the end of each section of the L-section trellis diagram, the branch complexity is defined as the number of parallel branches between two adjacent states, the state connectivity is defined in terms of the number of states which are adjacent to and from a given state and the connections between disjoint subsets of states, and the parallel structure is expressed in terms of the number of parallel sub-trellis diagrams without cross connections between them. This paper investigates the branch complexity, the state connectivity, and the parallel structure of an L-section minimal trellis diagram for a binary linear block code. First these complexities and structure are expressed in terms of the dimensions of specific subcodes of the given code. Then, the complexities of 2i-section minimal trellis diagrams for Reed-Muller codes are given.

41-56hit(56hit)