Comprensión Gauss ' fórmula de producto s citado en Golomb ' s secuencias de registro de cambio

Question

En su libro de Registro de Desplazamiento de las Secuencias, Solomon Golomb se refiere a "de Gauss, producto de la fórmula":

El dispositivo básico aquí es "de Gauss, fórmula de producto" [39], que expresa el "producto" de cualquiera de los dos cosets como una suma de cosets. (Este "producto" es en términos de evaluación con 1's y 0's. No tiene nada que ver con la multiplicación en el factor grupo.)

Estoy completamente perdido. ¿De qué está hablando? Los cosets aquí en Golomb del ejemplo son cyclotomic cosets $\bmod 2^N - 1$$N=5$, con

$$\begin{align} C_0 &= \{1,2,4,8,16\} \cr C_1 &= \{3,6,12,24,17\} \cr C_2 &= \{9,18,5,10,20\} \cr C_3 &= \{27,23,15,30,29\} \cr C_4 &= \{19,7,14,28,25\} \cr C_5 &= \{26,21,11,22,13\} \end{align}$$

Entiendo lo que estas cosets son (los elementos en el mismo coset son producidos por multiplicar por potencias de 2, $\bmod 2^N-1$), pero ¿cómo puede "multiplicar" o "agregar", y escribir las ecuaciones con respecto a $C_iC_j$?

Answer 1

La primera regla de mod $2$ es que el $\, x + x = 0 \,$ todos los $\,x.\,$ Aplicando esto a la dada Golomb ejemplo: $\, C_ 0 C_ 1 = C_ 0 + C_ 4 + C_ 5 + C_ 4 + C_ 2 = C_0 + C_2 + C_5 + (C_4 + C_4) = C_0 + C_2 + C_5 \pmod{2}.$

Su pregunta acerca de la multiplicación o adición de cosets es respondida de forma explícita por Golomb a sí mismo. Él dio la regla para multiplicar dos cosets para obtener una suma de cosets. La adición es "formal", además de cosets, salvo que se presenta el "mod $2$" de la regla. Por lo tanto cada suma de cosets se simplifica a una suma de distintas cosets. Estas reglas concretas se derivan en última instancia más abstracto y general de las normas.

Por ejemplo, en teoría de grupos finitos, una operación de multiplicación se define en las clases conjugacy donde el producto de dos clases conjugacy es la formal suma de clases conjugacy con entero positivo multiplicidad de los coeficientes en el caso de que una clase conjugacy aparece más de una vez en el formal de la suma.

La cuestión general de cómo podemos realizar operaciones llamadas de "adición" y "multiplicación" en general los objetos que podemos dar a las reglas abstractas acerca de cómo estas se realizan las operaciones y las reglas acerca de cómo determinar la igualdad entre los objetos. Este es el dominio de "álgebra abstracta".

Answer 2

Mi conjetura es que Golomb quería evitar el uso de estructuras de álgebra abstracta. Yo diría que este producto de la siguiente manera. Si se llega al final usted puede entender por qué Golomb quería utilizar su simple descripción! Hago esto porque de todos modos esto nos da muchas buenas propiedades del producto (por ejemplo, demostrando la asociatividad puede no ser evidente de lo contrario).

Todas estas operaciones aritméticas llevará a cabo en el cociente del anillo de polinomios con coeficientes en $\Bbb{F}_2$. Cuando se trata con cyclotomic cosets modulo $m$ (un número natural impar) usamos el anillo $$ R_m:=\Bbb{F}_2[x]/(x^m-1). $$ Usted puede haber visto este anillo se utiliza cuando se estudia cíclico códigos de longitud $m$ también. De todos modos, podemos ver una cyclotomic coset modulo $m$ como un elemento de $R_m$. Si $C$ es un cyclotomic coset, podemos pensar que es el polinomio $C(x)$ define simplemente como $$ C(x)=\sum_{i\in C}x^i. $$ Así, por ejemplo, en $R_{31}$ hemos $$ C_0(x)=x+x^2+x^4+x^8+x^{16} $$ y $$ C_1(x)=x^3+x^6+x^{12}+x^{24}+x^{17}. $$ Cuando usted multiplica los polinomios en el ring $R_{31}$ se multiplica casi como de costumbre polinomios. 1) Usted necesita para tener en cuenta que la media aritmética de los coeficientes se realiza modulo dos. 2) también debe tener en cuenta que la media aritmética de los exponentes se hace modulo $m$. Así que aquí por ejemplo $$ x^{16}\cdot x^{17}=x^{16+17}=x^{33}=x^{31+2}=x^2. $$ Tomando el cociente por $x^{31}-1$ hace exactamente eso: la equiparación de la $x^{31}$ con $1$, $x^{32}$ con $x$ et cetera.

Con el ejemplo. Cuando se calcula el producto $C_0(x)\cdot C_1(x)$ llegamos primero $$ \begin{aligned} &\left(x^{16}+x^8+x^4+x^2+x\right) \left(x^{24}+x^{17}+x^{12}+x^6+x^3\right)\\ =&x^{40}+x^{33}+x^{32}+2 x^{28}+x^{26}+2 x^{25}+x^{22}+x^{21}+x^{20}+2 x^{19}+x^{18}+x^{16}+2 x^{14}+x^{13}+x^{11}+x^{10}+x^8+2 x^7+x^5+x^4. \end{aligned} $$ La reducción de los exponentes modulo $31$ da $$ 2 x^{28}+x^{26}+2 x^{25}+x^{22}+x^{21}+x^{20}+2 x^{19}+x^{18}+x^{16}+2 x^{14}+x^{13}+x^{11}+x^{10}+x^9+x^8+2 x^7+x^5+x^4+x^2+x. $$ Como el toque final podemos entonces reducir los coeficientes modulo dos, y obtener el resultado: $$ x^{26}+x^{22}+x^{21}+x^{20}+x^{18}+x^{16}+x^{13}+x^{11}+x^{10}+x^9+x^8+x^5+x^4+x^2+x. $$ Verá que esta es la suma $$C_0(x)+C_2(x)+C_5(x)$$ como se había prometido.

He introducido una gran cantidad de exceso de equipaje. Esto no ayuda si usted hace la investigación con estas cosas. Confío en Golomb haber conocido a sus clientes, y hacer lo que él ve mejor pedagógicamente.