The combinatorics of reduced Grobner bases of certain zero-dimensional ideals, which arise when Grobner basis technique is applied to the soft-decision maximum likelihood decoding of binary linear block codes, will be...
详细信息
The combinatorics of reduced Grobner bases of certain zero-dimensional ideals, which arise when Grobner basis technique is applied to the soft-decision maximum likelihood decoding of binary linear block codes, will be studied. (C) 2003 Elsevier Inc. All rights reserved.
For a code C=C(n,M) the levelk code of C, denoted C-k, is the set of all vectors resulting from a linear combination of precisely k distinct codewords of C. We prove that if k is any positive integer divisible by 8, a...
详细信息
For a code C=C(n,M) the levelk code of C, denoted C-k, is the set of all vectors resulting from a linear combination of precisely k distinct codewords of C. We prove that if k is any positive integer divisible by 8, and n=gammak, M=betakgreater than or equal to2k then there is a codeword in C-k whose weight is either 0 or at most n/2 - n(1/8gamma - 6/(4beta-2)(2)) + 1. In particular, if gamma<(4beta-2)(2)/48 then there is a codeword in C-k whose weight is n/2-Theta(n). The method used to prove this result enables us to prove the following: Let k be an integer divisible by p, and let f(k,p) denote the minimum integer guaranteeing that in any square matrix over Z(p), of order f(k,p), there is a square submatrix of order k such that the sum of all the elements in each row and column is 0. We prove that lim inf f(k,2)/k<3.836. For general p we obtain, using a different approach, that f(k,p)less than or equal top((k / ln k)(1+o)((1)))(k).
This article is a survey of several recent applications of methods from analytic number theory to research in coding theory, including results on Kloosterman codes, binary Goppa codes, and prime phase shift sequences....
详细信息
This article is a survey of several recent applications of methods from analytic number theory to research in coding theory, including results on Kloosterman codes, binary Goppa codes, and prime phase shift sequences. The mathematical methods focus on exponential sums, in particular Kloosterman sums. The interrelationships with the Weil-Carlitz-Uchiyama bound, results on Hecke operators, theorems of Bombieri and Deligne and the Eichler-Selberg trace formula are reviewed.
The use of computer algebra is usually considered beneficial for mechanised reasoning in mathematical domains. We present a case study, in the application domain of coding theory, that supports this claim: the mechani...
详细信息
The use of computer algebra is usually considered beneficial for mechanised reasoning in mathematical domains. We present a case study, in the application domain of coding theory, that supports this claim: the mechanised proofs depend on non-trivial algorithms from computer algebra and increase the reasoning power of the theorem prover. The unsoundness of computer algebra systems is a major problem in interfacing them to theorem provers. Our approach to obtaining a sound overall system is not blanket distrust but based on the distinction between algorithms we call sound and ad hoc respectively. This distinction is blurred in most computer algebra systems. Our experimental interface therefore uses a computer algebra library. It is based on formal specifications for the algorithms, and links the computer algebra library Sumit to the prover Isabelle. We give details of the interface, the use of the computer algebra system on the tactic-level of Isabelle and its integration into proof procedures.
In this paper, we study residues of differential 2-forms on a smooth algebraic surface over an arbitrary field and give several statements about sums of residues. Afterwards, using these results, we construct algebrai...
详细信息
In this paper, we study residues of differential 2-forms on a smooth algebraic surface over an arbitrary field and give several statements about sums of residues. Afterwards, using these results, we construct algebraic-geometric codes which are an extension to surfaces of the well-known differential codes on curves. We also study some properties of these codes and extend to them some known properties for codes on curves. (C) 2009 Elsevier B.V. All rights reserved.
In this paper, we overview three closely related problems: Nelson-Hadwiger problem on coloring spaces with forbidden monochromatics distances;Borsuk's problem on partitioning sets in spaces into parts of smaller d...
详细信息
In this paper, we overview three closely related problems: Nelson-Hadwiger problem on coloring spaces with forbidden monochromatics distances;Borsuk's problem on partitioning sets in spaces into parts of smaller diameter;problem of finding codes with forbidden Hamming distances.
作者：
Kasai, TakumaKoshiba, SeizoYokoyama, JunKigawa, TakanoriRIKEN
Quantitat Biol Ctr QBiC Lab Biomol Struct & Dynam Tsurumi Ku Yokohama Kanagawa 2300045 Japan JST CREST
Tsurumi Ku Yokohama Kanagawa 2300045 Japan Tohoku Univ
Tohoku Med Megabank Org Aoba Ku Sendai Miyagi 9808573 Japan RIKEN
Innovat Ctr RInC Cell Free Technol Applicat Lab Tsurumi Ku Yokohama Kanagawa 2300045 Japan Taiyo Nippon Sanso Corp
SI Innovat Ctr Tama Tokyo 2060001 Japan Tokyo Inst Technol
Interdisciplinary Grad Sch Sci & Engn Dept Computat Intelligence & Syst Sci Midori Ku Yokohama Kanagawa 2268503 Japan
We describe a strategy for stable isotope-aided protein nuclear magnetic resonance (NMR) analysis, called stable isotope encoding. The basic idea of this strategy is that amino-acid selective labeling can be considere...
详细信息
We describe a strategy for stable isotope-aided protein nuclear magnetic resonance (NMR) analysis, called stable isotope encoding. The basic idea of this strategy is that amino-acid selective labeling can be considered as "encoding and decoding" processes, in which the information of amino acid type is encoded by the stable isotope labeling ratio of the corresponding residue and it is decoded by analyzing NMR spectra. According to the idea, the strategy can diminish the required number of labelled samples by increasing information content per sample, enabling discrimination of 19 kinds of non-proline amino acids with only three labeled samples. The idea also enables this strategy to combine with information technologies, such as error detection by check digit, to improve the robustness of analyses with low quality data. Stable isotope encoding will facilitate NMR analyses of proteins under non-ideal conditions, such as those in large complex systems, with low-solubility, and in living cells.
This article provides a tutorial introduction to the so-called two-part minimum description length (MDL) principle proposed by Rissanen. This two-part MDL principle is a powerful methodology for solving many statistic...
详细信息
This article provides a tutorial introduction to the so-called two-part minimum description length (MDL) principle proposed by Rissanen. This two-part MDL principle is a powerful methodology for solving many statistical model selection problems. However, it seems that this powerful methodology is only adopted by a small number of statisticians to tackle a small number of problems. One plausible reason for this is that the coding theory results required by the MDL principle are somewhat new to most statisticians, and that there are not many readily accessible articles introducing these results appearing in the statistical literature. The first part of this article is devoted to a discussion of such coding theory results. Then, in the second part of the article, the two-part MDL principle is introduced and explained. In doing so, only those coding theory results that are presented in the first part of the article are used. Finally, the applicability of the two-part MDL principle is demonstrated by applying it to tackle four different statistical problems.
Shannon's seminal 1948 work gave rise to two distinct areas of research: information theory and mathematical coding theory. While information theory has had a strong influence on theoretical neuroscience, ideas fr...
详细信息
Shannon's seminal 1948 work gave rise to two distinct areas of research: information theory and mathematical coding theory. While information theory has had a strong influence on theoretical neuroscience, ideas from mathematical coding theory have received considerably less attention. Here we take a new look at combinatorial neural codes from a mathematical coding theory perspective, examining the error correction capabilities of familiar receptive field codes (RF codes). We find, perhaps surprisingly, that the high levels of redundancy present in these codes do not support accurate error correction, although the error-correcting performance of receptive field codes catches up to that of random comparison codes when a small tolerance to error is introduced. However, receptive field codes are good at reflecting distances between represented stimuli, while the random comparison codes are not. We suggest that a compromise in error-correcting capability may be a necessary price to pay for a neural code whose structure serves not only error correction, but must also reflect relationships between stimuli.
We give a high-level overview of recent developments in interactive information and coding theory. These include developments involving interactive noiseless coding and interactive error-correction. The overview is pr...
详细信息
ISBN:
(纸本)9788961058070
We give a high-level overview of recent developments in interactive information and coding theory. These include developments involving interactive noiseless coding and interactive error-correction. The overview is primarily focused on developments related to complexity-theoretic applications, although the broader context and agenda are also set out. As the present paper is an extended abstract, the vast majority of proofs and technical details are omitted, and can be found in the respective publications and preprints.
暂无评论