Integer (1 Byte) Datentransformation DCT (FFT) gesucht

[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;

[Sinspin]

Zitat von Möbius:

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

Ausgezeichnet. Danke!

Ich habe mich vor einigen Jahren auch damit befasst und bin dann auf Gleitkomma ausgewichen mit anschließender Scalierung um wieder Integer zu bekommen.
Allerdings gab es immer eine unschöne (hörbare) Abweichung im wieder hergestellten Audiosignal. Mal sehen wie es mit der Methode funktioniert.

[Möbius]

Schön wenn es jemandem hilft.
Übrigens mein Code funktioniert auch in Place. D.h. die Copy kann man sich schenken. Hab's nur zum experimentieren drin gelassen.
Diese TIdatas ist übrigens ein Integer Array.
Wenn Du dies auf Audio anwendest dürften die Werte zwischendrin relativ hoch werden.
Ich hab das auch beobachtet.

[venice2]

Zitat:

Diese TIdatas ist übrigens ein Integer Array.

Schön zu hören.
Vielleicht solltest du diese Definition zu deinem Schnipsel hinzufügen ohne wären diese Sinnlos wenn man nicht weis wofür TIdatas steht.

[freimatz]

BTW: Welchen Sinn hat das Copy? Wird da nicht eh alles kopiert? Würde dann nicht Output := Data; reichen? Und wieso überhaupt Kopieren und nicht gleich auf Data arbeiten?

[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!

[Möbius]

Hallo Michael

Erst mal Danke für die guten Tipps.
Mein Kompressor-Projekt ist sehr sehr weit fortgeschrtten und kommt auf dem Calgary Corpus, Canterbury Corpus und Large Corpus mittlerweile an die Besten PPM (Prediction by Partial Matching) Kompressoren ran. Zeitlich sowieso, Zahlenmässig nah dran.
Also Artikel zur Huffman Komprimierung nützen mir nicht viel - diese ist Standard in meinen Programmen und wird final wohl noch durch die etwas bessere IntegerArithmetische Codierung ersetzt. Da muss man heute schon mehr bringen um was Neues zu machen.

Beim Kartenmischen muss ich widersprechen (Spektrum der Wissenschaft hin oder her - ich bin Abonennt). Ich bin mir mathematisch zwar nicht ganz sicher, aber konsequentes mischen (ein und dann aus) führt wohl irgendwann zu allen möglichen Permutationen der Karten. Von Ordnung kann hier nicht die Rede sein. Was heisst schon "Ordnung". Es ist eine Konvention was ordentlich ist. Jede Permutation stellt eine Art von Ordnung dar.

Nein die wirkliche Perfidie an RAD-Daten (Random-Daten) ist wirklich, dass diese statistischem Rauschen gleich kommen. Es gibt keine Zeichenwiederholungen, oder Wortbildungen o.ä. der einen Angriffspunkt gibt.
Ich habe mir für meine Forschungsplatform extra einen speziellen Zufallsgenerator gebaut. Der generiert nicht nur Zufallszahlen sondern erlaubt es, über weitere Zufallsgeneratoren, dass manchmal auch Zeichenwiederholngen oder Wortwiederholungen auftreten. Erstaunlich. Schon geringste Abweichungen vom absoluten Zufall führen zu interessanten komprimierten Ergebnissen.

Ich weiss ich weiss. Es gibt irgend ein Theorem/Beweis (ich weiss nicht mehr von wem), dass sich eine Zahlenmenge N nicht durch eine kleinere Zahlenmenge n vollständig abbilden lässt.
Der Beweis ist mir aber zu einfach. Schliesslich ist ja klar das Ordinalzahlen dazu dienen Kardinalzahlen abzuzählen. Also man braucht 1000 Ordinalzahlen um 1000 Karinalzahlen zu komprimieren.
Das ist aber imho falsch. Durch weglassen der führenden Nullen (was wir per Konvention im Alltag tun) lassen sich sehr viele Zahlen kürzer als 4 Stellen abbilden. Aber keine braucht bei dieser Ersparnis deswegen mehr als 4 Stellen.

Es scheint Du interessierst Dich für die Materie:
Dann schau mal hier über die Kolgomorov-Komplexizität nach: https://de.wikipedia.org/wiki/Kolmog...mplexit%C3%A4t
Du erwähnst Chaos. Chaos-Theorie auch bekannt? Es gibt "Gläubiger" die sagen man kann zu jeder Datenmenge N eine rekursive Formel finden, die diese Datenmenge erzeugt. Diese Formel sollte kürzer sein als die Datenmenge. Gut, dass hat noch keiner geschafft.
Aber deswegen halte ich es nicht für unmöglich.

Zur Informationstheorie letztlich.
Diese wurde bekanntlich von Claude Shannon in's Felde geführt und in den wesentlichsten Teilen von ihm ausgearbeitet.
Aber imho ist Sie noch lange nicht vollständig und zudem fehlerhaft.
Ein sehr grundlegender Fehler in der Theorie ist sicherich das Bit als grundlegendste Informationseinheit zu bennenen. Das Bit heisst neuerdings ja auch Shannon.
Aber es ist imho falsch. Es basiert auf dem binären Zahlensytem und wird von Computern nachgerade impliziert.
Aber es gäbe auch noch das unäre Zahlensystem. Das nur die Zahl Null kennt.
Mathematisch wahrscheinlich wenig sinnvoll, aber Informationstheoretisch?:
Es gibt zig Situationen in denen wir nicht per Information Ja/Nein oder 1/0 kommunizieren.
Es gibt zig Situationen in denen wir einfach per Information, Zeichen x senden, oder gar nicht, kommunizieren.
Z.B.
- Die alten Wikinger pflegten in Fijorden zu leben. An der Aussenseite des Fjordes haben Sie Wachposten angebracht welche Feinde entdecken sollen. Sind solche im Anmarsch haben Sie Meldefeuer entzündet welche das Dorf in der Bucht warnten. Das "Nichtbrennen" des Feuers kann aber schwerlich als permanentes senden von Nullen betrachtet werden.
- Oder, etwas salopp, der Playboy-Pfiff. Man läuft an einer Person vorbei und tut entweder gar nichts. D.h. aber nicht 0 (Null - Du bist ein Arsch oder interessierst mich nicht). Es heisst einfach gar nichts,. Gar nichts gesendet - auch keine 0. Aber eben der Pfiff = 1 der heisst schon einiges.

Also die Zukunft hat noch potential.