Hadamard code: Difference between revisions

Revision as of 19:13, 24 July 2016

Revision as of 19:18, 24 July 2016

Line 8:

| distance = <math>d=2^{k-1}</math>

| alphabet_size = <math>2</math>

| notation = <math>[2^{k},k,2^{k-1}]_2</math>-code

}}

{{infobox code

Line 14:

| namesake = [[Jacques Hadamard]]

| type = [[Linear code|Linear]] [[block code]]

| block_length = <math>n=2^{k-1}</math>

| message_length = <math>k+1</math>

| rate = <math>(k+1)/2^{k-1}</math>

| distance = <math>d=2^{k-21}</math>

| alphabet_size = <math>2</math>

| notation = <math>[2^{k-1},k+1,2^{k-21}]_2</math>-code

}}

[[File:Hadamard-Code.svg|thumb|right|250 px|Matrix of the Punctured Hadamard code (32, 6, 16) for the [[Reed–Muller code]] (1, 5) of the NASA space probe [[Mariner 9]]]]

[[File:Multigrade operator XOR.svg|thumb|250px|[[Exclusive or|XOR]] operations<br>Here the white fields stand for 0<br>and the red fields for 1]]

Line 32:

In standard [[Block code#Popular notation|coding theory notation]] for [[block code]]s, the Hadamard code is a <math>[2^k,k,2^{k-1}]_2</math>-code, that is, it is a [[linear code]] over a [[binary set|binary alphabet]], has [[Block code#The block length n|block length]] <math>2^k</math>, [[Block code#The message length k|message length]] (or dimension) <math>k</math>, and [[Block code#The distance d|minimum distance]] <math>2^k/2</math>.

The block length is very large compared to the message length, but on the other hand, errors can be corrected even in extremely noisy conditions.

The '''punctured Hadamard code''' is a slightly improved version of the Hadamard code; it is a <math>[2^{k-1},k+1,2^{k-21}]_2</math>-code and thus has a slightly better [[Block code#The rate R|rate]] while maintaining the relative distance of <math>1/2</math>, and is thus preferred in practical applications.

The punctured Hadamard code is the same as the first order [[Reed–Muller code]] over the binary alphabet.<ref>See, e.g., {{harvtxt|Guruswami|2009|p=3}}.</ref>