Integer (1 Byte) Datentransformation DCT (FFT) gesucht

[TiGü]

Aber es ist doch auch möglich, dass du dich beim Übersetzen vertan hast?!

Welches Codebeispiel hast du denn nach Delphi übersetzt?
Das Java- oder das C-Beispiel?!

[Möbius]

Ja könnte natürlich auch sein.

Hier die Übersetzungen (non integer):

Delphi-Quellcode:

class procedure TCompressOSCT.DCT(const Input: TFloat64Array; out Output: TFloat64Array);  //1 double[] DCT (double[] g) { // forward DCT on signal g
var
  M, mCnt, uCnt: Int64;
  s, cm, sums, Phi: Float64;
begin
  M := Length(Input); //2 int M = g.length;
  s := sqrt(2.0 / M); //3 double s = Math.sqrt(2.0 / M); // common scale factor
  SetLength(Output, M); //4 double[] G = new double[M];
  for mCnt := 0 to High(Input) do //5 for (int m = 0; m < M; m++) {
  begin
    cm := 1; // 6 double cm = 1.0;
    if mCnt = 0 then // 7 if (m == 0)
    begin
      cm := 1 / sqrt(2); // 8 cm = 1.0 / Math.sqrt(2);
    end;
    sums := 0; // 9 double sum = 0;
    for uCnt := 0 to High(Input) do // 10 for (int u = 0; u < M; u++) {
    begin
      Phi := Pi * mCnt * (2 * uCnt + 1) / (2 * M); //11 double Phi = Math.PI * m * (2 * u + 1) / (2 * M);
      sums := sums + (Input[uCnt] * cm * cos(Phi)); // 12 sum += g[u] * cm * Math.cos(Phi); }
    end;
    Output[mCnt] := s * sums; // 14 G[m] = s * sum; }
  end;
end;

class procedure TCompressOSCT.InvDCT(const Input: TFloat64Array; out Output: TFloat64Array);  // 20 double[] iDCT (double[] G) { // inverse DCT on spectrum G
var
  M, mCnt, uCnt: Int64;
  s, cm, sums, Phi: Float64;
begin
  M := Length(Input); // 21 int M = G.length;
  s := sqrt(2.0 / M); // 22 double s = Math.sqrt(2.0 / M); //common scale factor
  SetLength(Output, M); // 23 double[] g = new double[M];
  for uCnt := 0 to High(Input) do // 24 for (int u = 0; u < M; u++) {
  begin
    sums := 0; // 25 double sum = 0;
    for mCnt := 0 to High(Input) do //26 for (int m = 0; m < M; m++) {
    begin
      cm := 1; // 27 double cm = 1.0;
      if mCnt = 0 then // 28 if (m == 0)
      begin
        cm := 1 / sqrt(2); // 29 cm = 1.0 / Math.sqrt(2);
      end;
      Phi := Pi * mCnt * (2 * uCnt + 1) / (2 * M); // 30 double Phi = Math.PI * m * (2 * u + 1) / (2 * M);
      sums := sums + (Input[mCnt] * cm * cos(Phi)); // 31 sum += G[m] * cm * Math.cos(Phi); 32 }
    end;
    Output[uCnt] := s * sums; // 33 g[u] = s * sum; 34 }
  end;
end;

[freimatz]

"0 to High(Input)" - müsste das nicht -1 sein? Passt vermutlich. "Low(Input) to High(Input)" wäre schöner.

[TiGü]

Warum zwei geschachtelte Schleifen?
In der Wikipediadefintion von DCT-I bis DCT-IV sehe ich immer nur ein Summenzeichen?

[Blup]

Ich habe mal versucht zu optimieren.
Unnötige doppelte Operationen mit Hilfe von Zwischenvariablen aus Schleifen ziehen.
Multiplikation durch Addition ersetzen, wenn das möglich ist.
Ob das eine merkliche Verbesserung der Laufzeit bringt, müsste man in der Praxis testen.

Delphi-Quellcode:

class procedure TCompressOSCT.DCT(const Input: TFloat64Array; out Output: TFloat64Array);
var
  M, mCnt, uCnt: Int64;
  s, sums, Phi, Pi2M, Pi2MmCnt: Float64;
begin
  M := Length(Input);
  SetLength(Output, M);
  if M > 0 then
  begin
    s := sqrt(2.0 / M);
    Pi2M := Pi / (2 * M);
    Pi2MmCnt := 0;
    for mCnt := 0 to M - 1 do
    begin
      sums := 0;
      Phi  := Pi2MmCnt;
      for uCnt := 0 to M - 1 do
      begin
        sums := sums + (Input[uCnt] * cos(Phi));
        Phi := Phi + Pi2MmCnt + Pi2MmCnt;
      end;
      Output[mCnt] := s * sums;
      Pi2MmCnt := Pi2MmCnt + Pi2M;
    end;
    Output[0] := Output[0] / sqrt(2);
  end;
end;

Warum wird eigentlich ausgerechnet nur Output[0] durch sqrt(2) dividiert?

[Möbius]

@Freimatz
Nein das ist schon richtig so, Dynamische Arrays sind bei Delphi immer 0 basiert. D.h. Low(Array) und 0 sind äquivalent.

Vielen Dank für's optimieren, aber das Problem sind effekvtiv immer noch die 2 geschachtelten Schleifen. Ich rauch es aber sowieso Byte(Integer).

Eben wegen dieser "Sachlage". Ich arbeite schon einige Zeit an einem völlig neuartigen Kompressor und der hat mittlerweile echt gute Resultate. Bei Calgary und Canterbury Corpus kann er sicher vorne mitreden.
Aber es fehlt halt noch das i-Tüpfelchen.
Das Argument, dass man eine Nachricht N mit n Buchstaben nicht kürzer als N codieren kann, ohne dass man "Opfer" auf der anderen längeren Seite bringen muss, will mir nicht so recht in den Kopf.
Z.B. kann man ein Kartenspiel so lange perfekt mischen bis es sortiert ist. Dann braucht man bloss die Zahl der Mischvorgänge zu übermitteln um dies wieder rückgängig zu machen. Zauberkünstler nutzen diesen Trick übrigens für manche Kartenkunststücke. Man muss freilich die Kunst beherrschen ein Karttendeck wiederholt exakt in der mitte zu teilen und perfekt Karte links auf Karte rechts jeweils mischen können. Ein Deck mit 52 Karten ist verblüffender Weise nach 5 Durchgängen wieder sortiert.
Okay in der Praxis sind hier normalerweise viele Permutationen nötig.

Die Idee letztlich mit der FCT(Fast Cosinus Trandorm) jedenfalls könnte sich imho für völlig zufällige Daten eignen. Da rein zufällige Daten im Prinzip dem weissen Rauschen gleichkommen, müsste doch eigentlich eine Tranformation vom Zeitbereich in den Frequenzbereich ein Spektrum mit sehr kleinen Differenzen in den Amplituden der Spektralanteile liefern.
Das könnte schon ein interessanter input sein für irgended einen Codierer.

[Möbius]

Guten Tag zusammen

Also ich hab mal ein bisschen die Bücher gewälzt und so. Bin hier auf eine alternative orthogonale Transformation gestossen.
Die Walsh-Hadamard Transformation. Die funktioniert bestens mit Integer Werten.

Hier der Code falls das ma jemand brauchen könnte:

Delphi-Quellcode:

class procedure AClass.WalshHadamardTransform(var Data: TIDatas);
var
  i, j, n, m, x, y: UInt64;
  Output: TIDatas;
begin
  SetLength(Output, Length(Data));
  Output := Copy(Data, 0, Length(Data));
  n := Length(Data);
  m := 1;
  while 2 * m <= n do
  begin
    i := 0;
    while i < n do
    begin
      for j := i to i + m - 1 do
      begin
        x := Output[j];
        y := Output[j + m];
        Output[j] := y;
        Output[j + m] := x + y;
      end;
      i := i + 2 * m;
    end;
    m := m * 2;
  end;
  Data := Copy(Output, 0, Length(Output));
end;

class procedure AClass.InvWalshHadamardTransform(var Data: TIDatas);
var
  i, j, n, m, x, y: UInt64;
  Output: TIDatas;
begin
  SetLength(Output, Length(Data));
  Output := Copy(Data, 0, Length(Data));
  n := Length(Data);
  m := 1;
  while 2 * m <= n do
  begin
    i := 0;
    while i < n do
    begin
      for j := i to i + m - 1 do
      begin
        x := Output[j];
        y := Output[j + m];
        Output[j] := -x + y;
        Output[j + m] := x;
      end;
      i := i + 2 * m;
    end;
    m := m * 2;
  end;
  Data := Copy(Output, 0, Length(Output));
end;

[Michael II]

Zitat von Möbius:

Aber es fehlt halt noch das i-Tüpfelchen.
Das Argument, dass man eine Nachricht N mit n Buchstaben nicht kürzer als N codieren kann, ohne dass man "Opfer" auf der anderen längeren Seite bringen muss, will mir nicht so recht in den Kopf.
Z.B. kann man ein Kartenspiel so lange perfekt mischen bis es sortiert ist. Dann braucht man bloss die Zahl der Mischvorgänge zu übermitteln um dies wieder rückgängig zu machen. Zauberkünstler nutzen diesen Trick übrigens für manche Kartenkunststücke. Man muss freilich die Kunst beherrschen ein Karttendeck wiederholt exakt in der mitte zu teilen und perfekt Karte links auf Karte rechts jeweils mischen können. Ein Deck mit 52 Karten ist verblüffender Weise nach 5 Durchgängen wieder sortiert.
Okay in der Praxis sind hier normalerweise viele Permutationen nötig.

Hallo Möbius, erst einmal danke fürs Posten des Codes; dieser hilft sicher einigen weiter.

Zu Karten und Rauschen: Du wirfst Chaos (Rauschen) und Ordnung (Einmischen/Ausmischen) in den gleichen Topf.

Beim Kartenmischen - wie du es beschreibst - herrscht sehr grosse Ordnung - nur deshalb lässt sich mit ähnlich geordnetem "Zurückmischen" sehr rasch wieder die Ausgangsposition erreichen. Zum Thema Einmischen/Ausmischen findest du viele Infos im Web; u.a. hier.

Würdest du aus einem 52er Karten Set 52 Mal völlig zufällig genau eine Karte ziehen und auf einem neuen Stapel ablegen, dann hättest du diese Ordnung nicht.

Zum Rauschen und deiner Hoffnung dieses komprimieren zu können. Vergiss es . Ich empfehle dir, dich in Informationstheorie einzulesen. Dann sollte dir sehr rasch klar werden, dass dies nicht klappen kann.

Und wo eine gewisse Ordnung herrscht: Vielleicht hilft diese Seite einen Schritt weiter? Danach solltest du fast überzeugt sein, dass Gewinn auf der einen Seite (häufige Worte => kurze Codes), Verlust auf der anderen Seite (seltene Wörter => lange Codes) bedeutet. (Beispiel zum Link: Vollständiger binärer der Tiefe 5. Du kannst 2^5=32 Wörter an die 32 Blätter des Baums hängen. Damit codierst du jedes der 32 Worte mit 5 Bits. - Wenn du häufiger vorkommende Wörter mit weniger Bits codieren willst, dann benötigst du einen binären Baum mit Blättern näher der Wurzel. Du musst aber immer noch alle 32 Wörter an die Blätter deines Baums hängen können. D.h. du wirst deinen binären Baum anderswo erweitern müssen - und hast damit Wörter, welche du mit mehr als 5 Bits codierst.)

Sobald du fertig bist mit deiner "Möbius Kompression" wirst du hier hoffentlich einen Link auf dein Paper und dein Produkt posten. Viel Glück!