Begrenzung der Ausgabe des Rucksackalgorithmus auf die angegebene Bitgröße

Question

Momentan hat mein Professor eine Gruppenaufgabe gestellt, die es erfordert, Werte aus einem simulierten EKG-Scan zu nehmen und sie auf 8-Bit-Werte zu quantisieren. Von dort sollen wir die 8-Bit-Werte nehmen und sie durch einen Rucksack-Verschlüsselungsalgorithmus laufen lassen.

Ich habe kein Problem mit der Codierung, sondern eher eine Frage des Knapsacks selbst.

Wir verwenden einen Super-aufsteigenden Schlüssel, um unseren allgemeinen Schlüssel zu erstellen. Wir sollen die SIK-, m- und n-Werte berechnen. In diesem Fall wählte ich {1, 2, 5, 9, 22, 43, 118, 207} zu meinem SIK, da wir nur 8 Bits verwenden. Auch mein n = 19 und mein m = 511 (d. H. 19 * (was auch immer) mod511).

Dies erzeugt die resultierende Allgemeine Knapsack: {19, 38, 95, 171, 418, 306, 198, 356}

Das Problem kommt, wenn ich einen Wert verschlüsseln. Angenommen, ich verschlüssele etwas wie 10010111 Der resultierende Wert wäre 1050 (in Dezimal). Es wäre ein Problem, diesen Wert in meinen Quantizer zurückzusetzen, wenn man bedenkt, dass Dezimalwerte in 8-Bit-Binärwerte umgewandelt werden, was eine 10-Bit-Zahl ergibt.

Also spielte ich mit den Werten herum, änderte die SIK auf die kleinsten möglichen Werte und verschiedene Variationen von m und n, und trotzdem erhalte ich verschlüsselte Werte, die größer als 8 Bits sind.

Im Wesentlichen meine Frage ist das: Gibt es einen Wert für m und n, die ich verwenden könnte, die Werte im gewünschten Bitbereich (8 Bits) generieren würde, oder ist es mathematisch unmöglich? Der Professor sagte, er sei sich nicht sicher, ob es möglich sei, aber er dachte, es wäre so.

Ich könnte den Quantizer konvertieren, um größere Mengen von Bits zu nehmen, aber war nur neugierig zu sehen, ob das, was er fragte, sogar möglich war.

Answer 1

„Gibt es einen Wert für m und n, die ich, dass erzeugen Werte in dem gewünschten Bit-Bereich (8-Bit) würde verwenden könnte, oder ist es mathematisch unmöglich?“

kann es nicht beweisen unmöglich, aber ich werde aus einer praktischen Sicht sagen, es wird nicht funktionieren. Hier ist der Grund.

Da jedes Element mindestens doppelt so groß ist wie zuvor, bedeutet das, dass das 8. Element> = 2^8 = 256 sein muss. Folglich muss Ihr Modul m größer als 256 sein ist 9-Bits.

Jetzt dies zu arbeiten, müssen Sie einen Wert von n so finden, dass jede Teilmenge Summe der generierten Rucksack maximal 8-Bit (255 ist der größte Wert) sein. Der schlimmste Fall ist 11111111, wo alle Zahlen addiert werden. Die Elemente in Ihrem generierten Rucksack sind alle in der gleichen Reihenfolge wie Ihr Modul, der mindestens 9 Bits beträgt. Sie suchen also nach 8 Elementen, die nur die Reihenfolge von 9 Bits haben, in der Hoffnung, dass die Gesamtsumme 8 Bits beträgt. Es stimmt, ich habe es nicht als unmöglich bewiesen, aber ich hoffe, es gibt Ihnen ein Gefühl dafür, warum dies unwahrscheinlich ist.