Greedy generation of non-binary codes

摘要

We get a B-ordering of all binary n-tuples V_n bychoosing an ordered basis (y₁, …, y_n) of V_n and ordering the n-tuples as follows: 0, y₁, y₂, y₂+y₁, y₃,y₃+y₁, y₃+y₂,y₃+y₂+y₁, y₄, … .Given a minimum distance d, choose a set of vectors S with the zerovector first, then go through the vectors in their B-ordering and choosethe next vector which has distance d or more from all vectors alreadychosen. The surprising result that S is linear has been shown in severaldifferent ways. Linear codes found in this fashion are called greedycodes. We also look at the non-binary case. One can generalize theconcept of B-ordering to the case of an arbitrary base field. We alsolook at the parity check matrix