Was sind einige Beispiele für Nummerierungssysteme, für die es einfach ist, Permutationspolynome zu verallgemeinern?
Ich schreibe eine Aufgabe über Permutationspolynome (PP). Ich habe bereits einige Verallgemeinerungen und Charakterisierungen von PPs untersucht$\mathbb{Z}_p$ zum $p$ Primzahlen (und endliche Felder im Allgemeinen) und $\mathbb{Z}$. Ich suche nach einem anderen Nummerierungssystem zur Analyse, idealerweise nach einem, bei dem es einfach ist, eine allgemeine Form für jedes PP abzuleiten. Dies war für leicht zu erreichen$\mathbb{Z}$ unter Verwendung der grundlegenden Eigenschaften der Bewertungskarte und für $\mathbb{Z}_p$unter Verwendung von Lagrange-Interpolation + verwandten Techniken. Ich möchte, dass dieses Nummerierungssystem ein nicht endliches Feld oder ein kommutativer Ring mit Einheit ist. Wenn jemand irgendwelche Vorschläge hat, wäre es sehr dankbar.
Antworten
Folgendes fällt mir ein.
Quadratische Permutationspolynome auf $\Bbb{Z}_m$.
Lassen $m>1$sei eine ganze Zahl. Betrachten Sie die quadratische Polynomfunktion$$ f:\Bbb{Z}_m\to\Bbb{Z}_m, x\mapsto ax+bx^2. $$ Beweisen Sie Folgendes (es ist relativ einfach, fragen Sie, ob Sie einen Hinweis benötigen).
Lemma. Wenn$\gcd(a,m)=1$ und $b$ ist teilbar durch jeden Primfaktor von $m$, dann $f$ ist eine Permutation.
Der Grund, warum ich dies empfehle, ist, dass solche Permutationspolynome im LTE-Standard häufig als Turbo-Code-Interleaver verwendet werden (die Version des Standards, die 2009 fertiggestellt wurde, Aktualisierungen stehen noch aus, und dieser Teil wird wahrscheinlich veraltet sein). Mit anderen Worten, wenn meine Informationen nicht "veraltet" sind, berechnet Ihr Handy solche Permutationen wahrscheinlich einige Millionen Mal pro Sekunde. Die Version von LTE, an die ich mich erinnere, hat einen Wertebereich für angegeben$m$, jeweils teilbar durch eine relativ hohe Zweierpotenz und eine optimierte $(a,b)$ Paar für jedes solche $m$. Die Gründe für die Auswahl solcher Permutationen sind etwas technisch, aber ich denke, diese Anwendung ist zu cool, um sie zu bestehen.
Die Idee wurde in eingeführt
J. Sun und OY Takeshita, "Interleaver für Turbocodes unter Verwendung von Permutationspolynomen über ganzzahligen Ringen", IEEE Trans. Inf. Theory, vol.51, no. 1, S. 101–119, Januar 2005.
Dies steht hinter der IEEE-Paywall, aber hoffentlich hat Ihr Institut Zugriff. Wahrscheinlich sind alle Verweise auf 3GPP-Minuten und / oder Spezifikationen, die ich damals verwendet habe, veraltet. Als ich für den damals großen Cellplayer gearbeitet habe, habe ich die inversen Permutationen etwas intensiver studiert :-)