Main Article Content
Abstract
The purpose of this paper is to present a new and faster algorithmic procedure for generating the n bi Gray codes. Thereby, through this paper we have presented the derivation, design and implementation of a newly developed algorithm for the generation of an n-bit binary reflected Gray code sequences. The developed algorithm is stemmed from the fact of generating and properly placing the min-terms from the universal set of all the possible min-terms [m0 m1 m2 …. mN] of Boolean function of n variables, where, 0 < N < 2n-1. The resulting algorithm is in concise form and trivial to implement. Furthermore, the developed algorithm is equipped with added attributes of optimizing of time and space while executed.
Keywords
Article Details
References
- Alan, A., Bertossi, Alessandro, Mei., 2004, "Time and Work Optimal Simulation of Basic Reconfigurable Meshes on Hypercubes," J. of Parallel and Distributed Computing, Vol. 64(1), pp.173 - 180.
- Bitner, J., Ehrlich, G. and Reingold, E., 1976, 'Efficient Generation of the Binary Reflected Gray Code and its Applications," Communications of the ACM, Vol. 19(9), pp. 517-521.
- Black Paul, E., (2004), "Gray Code," NIST National Institute of Standards and Technology.
- Conway, J., Sloane, N. and Wilks, A., 1989, "Gray Codes and Reflection Groups," Graphs and Combinatorial, Vol. 5, pp. 315-325.
- Dominique Roelants van Baronaigien., 2000, "A Loopless Gray-Code Algorithm for Listing K-Array Trees," J. of Algorithms, Vol. 35(1), pp.100-107.
- Er, M.C., 1984, "On Generating the N-Array Reflected Gray Codes," IEEE transactions on computers, Vol. 33, pp. 739-741.
- Etzion, T., Paterson, K.G., 1996, "Near Optimal Single- Track Gray Codes," IEEE Trans. on Information Theory, Vol. 42(3), pp. 779-789.
- Goddyn, L., Gvozdjak, P., 2003, "Binary Gray Codes with Long Bit Runs," Electron. J. Combin. Vol. 10, pp. 1- 10.
- Gray, F., 1953, "Pulse Code Communication," United States Patent Number 2, 632, 058.
- Guan Dah-Jyu., 1998, "Generalized Gray Codes with Applications," Proceeding National Science Council of Republic of China, Vol. A(22), pp. 841 - 848.
- Hiltgen, P., Paterson, K. G. and Brandestini, M., 1996, "Single-Track Gray Codes," IEEE Trans. on Information Theory, Vol. 42(5), pp. 1555-1561.
- Jywe-Fei Fang , Kuan-Chou Lai, 2005, "Embedding the Incomplete Hypercube in Books," Information Processing Letters, Vol. 96(1), pp. 1-6.
- Lassing, E. G. Strom, T., Ottosson. and Agrell, E., (2003), "Computation of the Exact Bit Error rate of Coherent M-array PSK with Gray Code Bit Mapping," IEEE Transactions on Communications, Vol. 51(11), pp. 1758-1760.
- Lee, P. J., 1986, "Computation of the Bit Error Rate of Coherent M-array PSK with Gray Code Bit Mapping," IEEE Transactions on Communications, Vol. COM-34(5), pp. 488-491.
- Ludman, J. E., 1981, "Gray Code Generation for MPSK Signals," IEEE Transactions on Communications, Vol. COM-29(10), pp. 1519-1522.
- Moshe Schwartz and Tuvi Etzion, 1999, "The Structure of Single-Track Gray Codes," IEEE Transactions on Information Theory, Vol. 45(7), pp. 2383 - 2396.
- Figure 10. Run time requirements comparison Press, W.H., Flannery, B.P., Teukolsky, S. A. and Vetterling, W.T., 1992, "Gray Codes, Numerical Recipes in Fortran," Cambridge, England: Cambridge University Press, pp. 886-888.
- Proskurowski, A. and Ruskey, F., '1985, "Binary Tree Gray Codes," J. Algorithms 6, pp. 225-238.
- Ruskey, F., 1997, "A Survey of Venn Diagrams," Elec. J. of Comb, a special issue.
- Ruskey, F., 1993, "Simple Combinatorial Gray Codes Constructed by Reversing Sub-lists," Proceedings of the 4th International Symposium on Algorithms and Computation, p. 201-208, December 15-17.
- Savage, Carla., 1997, "A Survey of Combinatorial Gray Codes," Society of Industrial and Applied Mathematics Review, Vol. 39, pp. 605-629.
- Skiena, S., 1990, "Gray Code, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica," Reading, MA: Addison-Wesley, pp. 42-43 and 149.
- Sundberg, C. E., 1975, "Bit Error Probability Properties of Gray-coded M.P.S.K Signals," IEE Electronics Letters, Vol. 11(22), pp. 542-544.
- Vajnovszki, V. and Walsh, T.R., 2006, "A Loop-free two
References
Alan, A., Bertossi, Alessandro, Mei., 2004, "Time and Work Optimal Simulation of Basic Reconfigurable Meshes on Hypercubes," J. of Parallel and Distributed Computing, Vol. 64(1), pp.173 - 180.
Bitner, J., Ehrlich, G. and Reingold, E., 1976, 'Efficient Generation of the Binary Reflected Gray Code and its Applications," Communications of the ACM, Vol. 19(9), pp. 517-521.
Black Paul, E., (2004), "Gray Code," NIST National Institute of Standards and Technology.
Conway, J., Sloane, N. and Wilks, A., 1989, "Gray Codes and Reflection Groups," Graphs and Combinatorial, Vol. 5, pp. 315-325.
Dominique Roelants van Baronaigien., 2000, "A Loopless Gray-Code Algorithm for Listing K-Array Trees," J. of Algorithms, Vol. 35(1), pp.100-107.
Er, M.C., 1984, "On Generating the N-Array Reflected Gray Codes," IEEE transactions on computers, Vol. 33, pp. 739-741.
Etzion, T., Paterson, K.G., 1996, "Near Optimal Single- Track Gray Codes," IEEE Trans. on Information Theory, Vol. 42(3), pp. 779-789.
Goddyn, L., Gvozdjak, P., 2003, "Binary Gray Codes with Long Bit Runs," Electron. J. Combin. Vol. 10, pp. 1- 10.
Gray, F., 1953, "Pulse Code Communication," United States Patent Number 2, 632, 058.
Guan Dah-Jyu., 1998, "Generalized Gray Codes with Applications," Proceeding National Science Council of Republic of China, Vol. A(22), pp. 841 - 848.
Hiltgen, P., Paterson, K. G. and Brandestini, M., 1996, "Single-Track Gray Codes," IEEE Trans. on Information Theory, Vol. 42(5), pp. 1555-1561.
Jywe-Fei Fang , Kuan-Chou Lai, 2005, "Embedding the Incomplete Hypercube in Books," Information Processing Letters, Vol. 96(1), pp. 1-6.
Lassing, E. G. Strom, T., Ottosson. and Agrell, E., (2003), "Computation of the Exact Bit Error rate of Coherent M-array PSK with Gray Code Bit Mapping," IEEE Transactions on Communications, Vol. 51(11), pp. 1758-1760.
Lee, P. J., 1986, "Computation of the Bit Error Rate of Coherent M-array PSK with Gray Code Bit Mapping," IEEE Transactions on Communications, Vol. COM-34(5), pp. 488-491.
Ludman, J. E., 1981, "Gray Code Generation for MPSK Signals," IEEE Transactions on Communications, Vol. COM-29(10), pp. 1519-1522.
Moshe Schwartz and Tuvi Etzion, 1999, "The Structure of Single-Track Gray Codes," IEEE Transactions on Information Theory, Vol. 45(7), pp. 2383 - 2396.
Figure 10. Run time requirements comparison Press, W.H., Flannery, B.P., Teukolsky, S. A. and Vetterling, W.T., 1992, "Gray Codes, Numerical Recipes in Fortran," Cambridge, England: Cambridge University Press, pp. 886-888.
Proskurowski, A. and Ruskey, F., '1985, "Binary Tree Gray Codes," J. Algorithms 6, pp. 225-238.
Ruskey, F., 1997, "A Survey of Venn Diagrams," Elec. J. of Comb, a special issue.
Ruskey, F., 1993, "Simple Combinatorial Gray Codes Constructed by Reversing Sub-lists," Proceedings of the 4th International Symposium on Algorithms and Computation, p. 201-208, December 15-17.
Savage, Carla., 1997, "A Survey of Combinatorial Gray Codes," Society of Industrial and Applied Mathematics Review, Vol. 39, pp. 605-629.
Skiena, S., 1990, "Gray Code, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica," Reading, MA: Addison-Wesley, pp. 42-43 and 149.
Sundberg, C. E., 1975, "Bit Error Probability Properties of Gray-coded M.P.S.K Signals," IEE Electronics Letters, Vol. 11(22), pp. 542-544.
Vajnovszki, V. and Walsh, T.R., 2006, "A Loop-free two