مرکز منطقه ای اطلاع رساني علوم و فناوري - On the covering radius of binary, linear codes meeting the Griesmer bound

DocumentCode :

940528

Title :

On the covering radius of binary, linear codes meeting the Griesmer bound

Author :

Busschbach, Peter B. ; Gerretzen, Michiel G L ; Van Tilborg, Henk C A

Volume :

Issue :

fYear :

1985

fDate :

7/1/1985 12:00:00 AM

Firstpage :

465

Lastpage :

468

Abstract :

Let $g(k, d) = \\sum _{i=0}^{k-1} \\lceil d / 2^{i} \\rceil$ . By the Griesmer bound, $n \\geq g(k, d)$ for any binary, linear $[n, k, d]$ code. Let $s = \\lceil d / 2^{k-1} \\rceil$ . Then, $s$ can be interpreted as the maximum number of occurrences of a column in the generator matrix of any code with parameters $[g(k, d), k, d]$ . Let $\\rho$ be the covering radius of a [g(k, d), k, d] code. It will be shown that $\\rho \\leq d - \\lceil s / 2 \\rceil$ . Moreover, the existence of a $[g(k, d), k, d]$ code with $\\rho = d - \\lceil s / 2 \\rceil$ is equivalent to the existence of a $[g(k + 1, d), k + 1, d]$ code. For $s \\leq 2$ , all $[g(k,d),k,d]$ codes with $\\rho = d - \\lceil s / 2 \\rceil$ are described, while for $s > 2$ a sufficient condition for their existence is formulated.