An optimal code for patient identifiers

How to distinguish 1 billion individuals by an identifier consisting of eight characters, allowing a reasonable amount of error detection or even error correction? Our solution of this problem is an optimal code over a 32-character alphabet that detects up to two errors and corrects one error as well as a transposition of two adjacent characters. The corresponding encoding and error checking algorithms are available for free; they are also embedded as components of the pseudonymisation service that is used in the TMF-the German telematics platform for health research networks.     

A characterization of MMD codes

Let C be a linear [n,k,d]-code over GF(q) with k⩾2. If s=n-k+1-d denotes the defect of C, then by the Griesmer bound, d⩽(s+1)q. Now, for obvious reasons, we are interested in codes of given defect s for which the minimum distance is maximal, i.e., d=(s+1)q. We classify up to formal equivalence all such linear codes over GF(q). Remember that two codes over GF(q) are formally equivalent if they have the same weight distribution. It turns out that for k⩾3 such codes exist only in dimension 3 and 4 with the ternary extended Golay code, the ternary dual Golay code, and the binary even-weight code as exceptions. In dimension 4 they are related to ovoids in PG(3,q) except the binary extended Hamming code, and in dimension 3 to maximal arcs in PG(2,q)