✦ LIBER ✦

On Identifying Codes in Binary Hamming Spaces

✍ Scribed by Iiro Honkala; Antoine Lobstein

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 138 KB
Volume: 99
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.2002.3263

No coin nor oath required. For personal study only.

✦ Synopsis

A binary code C f0; 1g n is called r-identifying, if the sets B r ðxÞ \ C; where B r ðxÞ is the set of all vectors within the Hamming distance r from x; are all nonempty and no two are the same. Denote by M r ðnÞ the minimum possible cardinality of a binary r-identifying code in f0; 1g n : We prove that if r 2 ½0; 1Þ is a constant, then lim n!1 n À1 log 2 M b rnc ðnÞ ¼ 1 À H ðrÞ; where H ðxÞ ¼ Àx log 2 x À ð1 À xÞ log 2 ð1 À xÞ: We also prove that the problem whether or not a given binary linear code is r-identifying is P 2 -complete.

📜 SIMILAR VOLUMES

On the Density of Identifying Codes in t

On the Density of Identifying Codes in the Square Lattice

✍ Iiro Honkala; Antoine Lobstein 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 148 KB

Let G=(V, E) be an undirected graph and C a subset of vertices. If the sets B r (v) 5 C, v ¥ V, are all nonempty and different, where B r (v) denotes the set of all points within distance r from v, we call C an r-identifying code. We give bounds on the best possible density of r-identifying codes in

Gallager bounds on the performance of ma

Gallager bounds on the performance of maximum-likelihood decoded linear binary block codes in AWGN interference

✍ Yousefi, Shahram 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 278 KB

There exist Steiner triple systems of or

There exist Steiner triple systems of order 15 that do not occur in a perfect binary one-error-correcting code

✍ Patric R. J. Östergård; Olli Pottonen 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 74 KB 👁 1 views

## Abstract The codewords at distance three from a particular codeword of a perfect binary one‐error‐correcting code (of length 2^m^−1) form a Steiner triple system. It is a longstanding open problem whether every Steiner triple system of order 2^m^−1 occurs in a perfect code. It turns out that thi

Design criteria for space-time trellis c

Design criteria for space-time trellis codes based on product distance distribution and trace distribution in fast fading channels

✍ Yukihiro Sasazaki; Tomoaki Ohtsuki 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 487 KB

A personal perspective on research, cons

A personal perspective on research, consulting and codes/standards development in fire-related human behaviour, 1969–1999, with an emphasis on space and time factors

✍ Jake Pauls 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 2 views

Four phases of work in the 5re-related human behaviour 5eld are described. Falling into the 5rst phase was the author:s early research into human behaviour in 5re (which was most well known for its focus on evacuation); it began several years before the 5rst international meetings were held in the U