Inverse hyperbolic function: Difference between revisions

Revision as of 12:41, 17 November 2013

The Johnson bound is a limit on the size of error-correcting codes, as used in coding theory for data transmission or communications.

Definition

Let $C$ be a q-ary code of length $n$ , i.e. a subset of $𝔽_{q}^{n}$ . Let $d$ be the minimum distance of $C$ , i.e.

d = \min_{x, y \in C, x \neq y} d (x, y)

,

where $d (x, y)$ is the Hamming distance between $x$ and $y$ .

Let $C_{q} (n, d)$ be the set of all q-ary codes with length $n$ and minimum distance $d$ and let $C_{q} (n, d, w)$ denote the set of codes in $C_{q} (n, d)$ such that every element has exactly $w$ nonzero entries.

Denote by $| C |$ the number of elements in $C$ . Then, we define $A_{q} (n, d)$ to be the largest size of a code with length $n$ and minimum distance $d$ :

A_{q} (n, d) = \max_{C \in C_{q} (n, d)} | C | .

Similarly, we define $A_{q} (n, d, w)$ to be the largest size of a code in $C_{q} (n, d, w)$ :

A_{q} (n, d, w) = \max_{C \in C_{q} (n, d, w)} | C | .

Theorem 1 (Johnson bound for $A_{q} (n, d)$ ):

If $d = 2 t + 1$ ,

A_{q} (n, d) \leq \frac{q^{n}}{\sum_{i = 0}^{t} (\binom{n}{i}) (q - 1)^{i} + \frac{(\binom{n}{t + 1}) (q - 1)^{t + 1} - (\binom{d}{t}) A_{q} (n, d, d)}{A_{q} (n, d, t + 1)}} .

If $d = 2 t$ ,

A_{q} (n, d) \leq \frac{q^{n}}{\sum_{i = 0}^{t} (\binom{n}{i}) (q - 1)^{i} + \frac{(\binom{n}{t + 1}) (q - 1)^{t + 1}}{A_{q} (n, d, t + 1)}} .

Theorem 2 (Johnson bound for $A_{q} (n, d, w)$ ):

(i) If $d > 2 w$ ,

A_{q} (n, d, w) = 1 .

(ii) If $d \leq 2 w$ , then define the variable $e$ as follows. If $d$ is even, then define $e$ through the relation $d = 2 e$ ; if $d$ is odd, define $e$ through the relation $d = 2 e - 1$ . Let $q^{*} = q - 1$ . Then,

A_{q} (n, d, w) \leq ⌊ \frac{n q^{*}}{w} ⌊ \frac{(n - 1) q^{*}}{w - 1} ⌊ \dots ⌊ \frac{(n - w + e) q^{*}}{e} ⌋ \dots ⌋ ⌋

where $⌊ ⌋$ is the floor function.

Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on $A_{q} (n, d)$ .

References

S. M. Johnson, "A new upper bound for error-correcting codes," IRE Transactions on Information Theory, pp. 203–207, April 1962.
W. Cary Huffman, Vera Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003.

@@ Line 1: / Line 1: @@
-Hi there. Allow me start by introducing the writer, her title is Sophia. To climb is some thing she would by no means give up. She works as a journey agent but quickly she'll be on her own. Ohio is where her house is.<br><br>my web blog - certified psychics ([http://cspl.postech.ac.kr/zboard/Membersonly/144571 Learn Alot more])
+The '''Johnson bound''' is a limit on the size of [[error-correcting code]]s, as used in [[coding theory]] for [[data transmission]] or communications.
+== Definition ==
+Let <math>C</math> be a q-ary [[code]] of length <math>n</math>, i.e. a subset of <math>\mathbb{F}_q^n</math>. Let <math>d</math> be the minimum distance of <math>C</math>, i.e.
+:<math>d = \min_{x,y \in C, x \neq y} d(x,y)</math>&nbsp;,
+where <math>d(x,y)</math> is the [[Hamming distance]] between <math>x</math> and <math>y</math>.
+Let <math>C_q(n,d)</math> be the set of all q-ary codes with length <math>n</math> and minimum distance <math>d</math> and let <math>C_q(n,d,w)</math> denote the set of codes in <math>C_q(n,d)</math> such that every element has exactly <math>w</math> nonzero entries.
+Denote by <math>|C|</math> the number of elements in <math>C</math>. Then, we define <math>A_q(n,d)</math> to be the largest size of a code with length <math>n</math> and minimum distance <math>d</math>:
+:<math> A_q(n,d) = \max_{C \in C_q(n,d)} |C|.</math>
+Similarly, we define <math>A_q(n,d,w)</math> to be the largest size of a code in <math>C_q(n,d,w)</math>:
+:<math> A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|.</math>
+<strong>Theorem 1 (Johnson bound for <math>A_q(n,d)</math>):</strong>
+If <math>d=2t+1</math>,
+:<math> A_q(n,d) \leq \frac{q^n}{\sum_{i=0}^t {n \choose i} (q-1)^i + \frac{{n \choose t+1} (q-1)^{t+1} - {d \choose t} A_q(n,d,d)}{A_q(n,d,t+1)} }. </math>
+If <math>d=2t</math>,
+:<math> A_q(n,d) \leq \frac{q^n}{\sum_{i=0}^t {n \choose i} (q-1)^i + \frac{{n \choose t+1} (q-1)^{t+1} }{A_q(n,d,t+1)} }. </math>
+<strong> Theorem 2 (Johnson bound for <math>A_q(n,d,w)</math>):</strong>
+<strong>(i)</strong> If <math>d > 2w</math>,
+:<math> A_q(n,d,w) = 1. </math>
+<strong>(ii)</strong> If <math>d \leq 2w</math>, then define the variable <math>e</math> as follows. If <math>d</math> is even, then define <math>e</math> through the relation <math>d=2e</math>; if <math>d</math> is odd, define <math>e</math> through the relation <math>d = 2e - 1</math>.  Let <math>q^* = q - 1</math>. Then,
+:<math> A_q(n,d,w) \leq \lfloor \frac{n q^*}{w}  \lfloor \frac{(n-1)q^*}{w-1} \lfloor \cdots \lfloor \frac{(n-w+e)q^*}{e} \rfloor \cdots \rfloor \rfloor </math>
+where <math>\lfloor ~~ \rfloor</math> is the [[floor function]].
+<strong>Remark:</strong> Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on <math>A_q(n,d)</math>.
+==See also==
+* [[Singleton bound]]
+* [[Hamming bound]]
+* [[Plotkin bound]]
+* [[Elias Bassalygo bound]]
+* [[Gilbert–Varshamov bound]]
+* [[Griesmer bound]]
+==References==
+* S. M. Johnson, "A new upper bound for error-correcting codes," ''IRE Transactions on Information Theory'', pp.&nbsp;203–207, April 1962.
+* W. Cary Huffman, [[Vera Pless]], ''Fundamentals of Error-Correcting Codes'', Cambridge University Press, 2003.
+[[Category:Coding theory]]

Inverse hyperbolic function: Difference between revisions

Revision as of 12:41, 17 November 2013

Definition

See also

References

Navigation menu

Search