Error correction coding is provided for codeword headers in a data tape format, such as a Linear Tape-Open, Generation 4 (LTO-4) data tape format. The data tape format defines a codeword quad as having first and second codeword headers interleaved with first and second codeword pairs, each codeword header comprising N bytes ck=c0, c1, . . . , cN−2, cN−1 wherein K bytes c0-cK−1 of the first and second headers in a codeword quad differ such that if one is known the other can be inferred. Each header byte ck of a codeword quad is redefined as comprising two interleaved (m/2)-bit nibbles, ek, ok. For each header, nibbles eK-eN−1 and nibbles oK-oN−1 are generated as a function of nibbles, e0-eK−1 and o0-oK−1, respectively. A codeword is assembled with the redefined headers the codeword quad is then recorded onto a recording medium.