Charly_cs,

ja, Dein Weg ist gangbar. Du musst nur aufpassen, dass die Integers lang genug sind, um die grösste vorkommende Zahl ohne Überlauf aufnehmen zu können.

Es gibt noch einen anderen Weg: Nimm einfach die Fast-Hadamard-Transformation (FHT) und rechne das Ergebnis anschliessend in Fourier-Koeffizienten um. Das ist vorteilhaft, weil die FHT nur mit Subtraktionen und Additionen und ohne Drehfaktor-Tabelle auskommt. Weil die Hadamard-Funktionen (sind eigentlich Walsh-Funktionen) ein orthogonales Funktionensystem bilden, ist die Abbildung auf den Fourierkoeffizienten ein-eindeutig. Du kannst also ohne Informationsverlust hin- und zurücktransformieren. Deshalb ist auch die Transformationsmatrix Hadamard->Fourierkoeffizienten symmetrisch. Es genügt also, die obere rechte Dreiecksmatrix zu berechnen. Ich würde die Werte im Voraus auf dem PC berechnen und dann als Tabelle im Programmspeicher des AVR ablegen.

mare_crisium