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.