Rao or (Dual) Hamming Bound
Every orthogonal array OA(M, s, Sb, k) with k even satisfies the Rao-bound [1], namely
where Vbs(r) denotes the volume of a ball with radius r in the Hamming space Sbs.
The dual to this bound is known as Hamming bound or sphere-packing bound. It states that the condition given above with M = bs/N holds for every (s, N, k + 1)-code over Fb, i.e., that
It is easily established by noting that the N balls of radius k/2 (in Hamming space) centered at the N code words must be disjoint in Fbs.
It is now known that the Rao bound is implied by the linear programming bound and that it can be generalized to OOAs with arbitrary depth T .
Codes and Orthogonal Arrays Meeting these Bounds
Orthogonal arrays meeting the Rao bound with equality are called tight, whereas codes meeting the sphere packing bound are called perfect. Therefore, the dual of every perfect linear code is a tight linear orthogonal array and vice versa.
The only linear perfect codes are [s, s, 1]-codes without redundancy (minimum distance d = 1), Hamming codes (minimum distance d = 3), the binary and ternary Golay code (minimum distance d = 7 and d = 5, respectively), and binary [s, 1, s]-repetition codes with d = s odd. The only tight linear orthogonal arrays are the duals of these codes.
If a perfect (s, N, d)-code can be extended to an (s + 1, N, d + 1)-code, the extended code is called nearly perfect. Every nearly perfect code can be truncated to a perfect code. The opposite is only true over F2, where every perfect code can be extended to a nearly perfect code by adding a parity check bit.
The only linear nearly perfect codes are [s + 1, s, 2]-parity check codes (minimum distance d = 2), extended binary Hamming codes (minimum distance d = 4), the binary and ternary extended Golay code (minimum distance d = 8 and d = 6, respectively), and binary [s, 1, s]-repetition codes with d = s even.
Application to Nets and Sequences
In [2, Proposition 1] the Hamming Bound is used for establishing a bound for digital nets.
By considering digital (t, t + k, s + 1)-nets over Fb with k = ⌊t log q⌋ + 1, it is shown in [2, Corollary 2] that db(s), defined as the minimum t such that a digital (t, s)-sequence over Fb exists, satisfies
s – O(1). Therefore, db(s) grows a least linearly in s. Using the Rao Bound instead of the Hamming bound, the same results can be proven for nets and sequences which are not necessarily digital.
Stronger bounds for sequences can be derived from the generalized Rao Bound for OOAs and nets since it takes the full depth T = k of the net into account, the (dual) Plotkin bound because it is stronger than the Rao bound for t≪m, and the generalized (dual) Plotkin bound for OOAs because it combines these two properties.
See also
Generalization for arbitrary OOAs
Corresponding result for nets
[3, Ch. 1, Th. 6]
Perfect code at
References
| [1] | Calyampudi Radhakrishna Rao. Factorial experiments derivable from combinatorial arrangements of arrays. Supplement to the Journal of the Royal Statistical Society, 9:128–139, 1947. |
| [2] | Harald Niederreiter and Chaoping Xing. Low-discrepancy sequences obtained from algebraic function fields over finite fields. Acta Arithmetica, 72(3):281–298, 1995. MR1347491 (96g:11099) |
| [3] | F. Jessie MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977. |
Copyright
Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Rao or (Dual) Hamming Bound.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2024-09-05.
http://mint.sbg.ac.at/desc_CBoundRao.html