Geodesic
Bijective mappings generated by filtering generator
Prikladnaâ diskretnaâ matematika, no. 1 (2014), pp. 27-39.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper deals with the methods for constructing bijective mappings $ B_{f,L}$ whose coordinate functions are defined by a great length shift register with a feedback function $L(x_1,x_2,\ldots,x_n)$ and with an output (filtering) nonlinear function $f(x_1,x_2,\ldots,x_k)$ depending on a small number $k$ of its arguments $(k\ll n).$ It is known that the orthogonality of the coordinate functions is equivalent to the bijectiveness of the mapping $B_{f,L}$. A method developed in the paper reduces the problem of bijectiveness of $B_{f,L}$ for any $n$ to the case of bounded $n$. The method allows to build new infinite classes of bijective mappings $B_{f,L}$ for nonlinear functions $f$ depending on four, five or six variables. Earlier, similar results were known for a function $f$ depending on three arguments. The results can be useful for constructing and proving statistical properties of random sequences generated on the basis of filter generators.
Keywords: orthogonal system of Boolean functions, feedback shift register, filter generator. 
@article{PDM_2014_1_a3,
     author = {M. I. Rozhkov},
     title = {Bijective mappings generated by filtering generator},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {27--39},
     publisher = {mathdoc},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_1_a3/}
}
TY  - JOUR
AU  - M. I. Rozhkov
TI  - Bijective mappings generated by filtering generator
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 27
EP  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_1_a3/
LA  - ru
ID  - PDM_2014_1_a3
ER  - 
%0 Journal Article
%A M. I. Rozhkov
%T Bijective mappings generated by filtering generator
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 27-39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2014_1_a3/
%G ru
%F PDM_2014_1_a3
M. I. Rozhkov. Bijective mappings generated by filtering generator. Prikladnaâ diskretnaâ matematika, no. 1 (2014), pp. 27-39. http://geodesic.mathdoc.fr/item/PDM_2014_1_a3/

[1] Lidl R., Niderraiter G., Konechnye polya, v 2-kh t., Mir, M., 1988, 822 pp. | Zbl

[2] Rozhkov M. I., “K voprosu postroeniya ortogonalnykh sistem dvoichnykh funktsii s ispolzovaniem registra sdviga”, Lesnoi vestnik, 2011, no. 3, 180–185

[3] Huffman D. A., “Canonical forms for information loss less finite state logical mashines”, IRE Trans. Circuit Theory, 6, Spec. suppl. (1959), 41–59 | DOI | Zbl

[4] Sumarokov S. N., “Zaprety dvoichnykh funktsii i obratimost dlya odnogo klassa kodiruyuschikh ustroistv”, Obozrenie prikl. i promyshl. matem. Ser. diskretn. matem., 1:1 (1994), 33–35

[5] Logachev O. A., Smyshlyaev S. V., Yaschenko V. V., “Novye metody izucheniya sovershenno uravnoveshennykh bulevykh funktsii”, Diskretnaya matematika, 21:2 (2009), 51–74 | DOI | MR | Zbl

[6] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, Uchebnik. V 2-kh t., v. 2, Gelios ARV, M., 2003, 416 pp.

[7] Sarantsev A. V., “Postroenie regulyarnykh sistem odnotipnykh dvoichnykh funktsii s ispolzovaniem registra sdviga”, Lesnoi vestnik, 2004, no. 1(32), 164–169

[8] Rozhkov M. I., “Nekotorye algoritmicheskie voprosy identifikatsii konechnykh avtomatov po raspredeleniyu vykhodnykh $m$-gramm. Ch. 2”, Obozrenie prikl. i promyshl. matem. Ser. diskretn. matem., 15:5 (2008), 785–806

[9] Rozhkov M. I., “Nekotorye algoritmicheskie voprosy identifikatsii konechnykh avtomatov po raspredeleniyu vykhodnykh $m$-gramm. Ch. 3”, Obozrenie prikl. i promyshl. matem. Ser. diskretn. matem., 16:1 (2009), 35–60

[10] Mikhailov V. G., Chistyakov V. P., “O zadachakh teorii konechnykh avtomatov, svyazannykh s chislom proobrazov vykhodnoi posledovatelnosti”, Obozrenie prikl. i promyshl. matem. Ser. diskretn. matem., 1:1 (1994), 7–32 | Zbl

[11] Fomichev V. M., Diskretnaya matematika i kriptologiya, Kurs lektsii, ed. N. D. Podufalov, DIALOG-MIFI, M., 2003, 400 pp.

[12] Rozhkov M. I., “O nekotorykh klassakh nelineinykh registrov sdviga, obladayuschikh odinakovoi tsiklovoi strukturoi”, Diskretnaya matematika, 22:2 (2010), 96–119 | DOI | MR | Zbl