Sadly, when I think to compare my elegant serendipitous discovery against the Hamming bound, I find that a random binary code detecting 6 errors in length 20 blocks should expect to notch up size between 17 and 48 blocks; so size n = 6 (second example) looks some way short of perfection. More Jimmy Durante than Arthur Sullivan, then! Fred Lunnon On 4/25/19, Fred Lunnon <fred.lunnon@gmail.com> wrote:
(Revised, sans Sir Arthur Sullivan, Jimmy Durante etc.)
Example n,m = 6,3 of an elementary binary block code which I provisionally christen the "(n, m) Combination Code" :
1 0 0 0 1 1 1 0 0 0 * 1 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 * 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 * 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 * 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 * 1 1 1 0 0 0 1 1 1 0 * * * * * * * * * * * * * * * * * * * * * * * * * 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
The general case boasts statistics:
blocks = n (rows), weight = (n-1)_C_(m-1) , length = n_C_m , distance = 2 (n-2)_C_(m-1) , rank = n ,
where n_C_m denotes binomial coefficient.
Proofs of values claimed above follow by induction on m and n , noting that the columns comprise combinations of m from n represented as binary strings: the inductive decomposition into smaller codes is indicated in the example, modulo customary email corruption by proportional spacing, spurious line breaks, etc.
A permutation on the n rows of the codeword set leaves it invariant, but also induces a permutation on code digits: hence the code is invariant under the symmetric group of order n , acting simultaneously on codewords and (inversely) on their bits.
I wonder if the construction generalises from binary to k-ary digits, by substituting bag permutations for combinations ...
Efficient decoding is hardly a consideration, assuming that in practice n would necessarily be small.
Anyway, there you go, folks --- enjoy my modest contribution to coding theory before it sinks irrevocably from view; or somewhere a real expert gets out of bed and disabuses me.
Fred Lunnon
On 4/23/19, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Seated one day at an analogue of the aperiodic Penrose tiling, I struck one 10-dimensional rank-4 null space of beauty with the (redundant) weight-4 basis:
[ 1, 0, 0, 0, -1, -1, -1, 0, 0, 0] [ 0, 1, 0, 0, -1, 0, 0, 0, -1, 1] [ 0, 0, 1, 0, 0, -1, 0, 1, 0, -1] [ 0, 0, 0, 1, 0, 0, -1, -1, 1, 0] [ 1, -1, -1, -1, 0, 0, 0, 0, 0, 0] ;
and on dropping signs it struck me (back!) that this was case n,m = 5,2 of an elementary binary block code with:
number = n words, weight = (n-1)_C_(m-1) , length = n_C_m , distance = 2 (n-2)_C_(m-1) ,
where n_C_m denotes binomial coefficient.
I have sought, but I seek it vainly --- along with its name and rank. Can somebody please jog my memory?
Fred Lunnon