X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/3fc31015143d2bab7226a54390f3e1c5eba8f4d5..dc38289efffc51c12872f9b0be76aefc25b32a05:/hamilton.tex?ds=sidebyside

diff --git a/hamilton.tex b/hamilton.tex
index 32888bd..a48fc62 100644
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -7,7 +7,7 @@ the number of transitions of each element must differ
 at most by 2.
 This uniformity is a global property on the cycle, \textit{i.e.},
 a property that is established while traversing the whole cycle.
-On the opposite side, when the objective is to follow a subpart 
+On the other hand, when the objective is to follow a subpart 
 of the Gray code and to switch each element approximately the 
 same amount of times,
 local properties are wished.
@@ -21,11 +21,11 @@ $b$ times to produce a pseudorandom number,
 \textit{i.e.}, a vertex in the 
 $\mathsf{N}$-cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 
-to provide an uniform output distribution.
+to provide a uniform output distribution.
 To reduce the number of iterations, it can be claimed
 that the provided Gray code
 should ideally possess both balanced and locally balanced properties.
-However, none of the two algorithms is compatible with the second one:
+However, both algorithms are incompatible with the second one:
 balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
 locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
 are not globally balanced.
@@ -40,13 +40,13 @@ namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96},
 and~\cite{ZanSup04} have addressed the problem of providing an approach
 to produce balanced gray code.
 The authors of~\cite{Robinson:1981:CS} introduced an inductive approach
-aiming at producing balanced Gray codes, provided the user gives 
+aiming at producing balanced Gray codes, assuming the user gives 
 a special subsequence of the transition sequence at each induction step.
-This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
-where the authors have explicitly shown how to construct such a subsequence.
+This work has been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
+where the authors have explicitly shown how to build such a subsequence.
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
-algorithm. Their rigorous presentation of this one 
+algorithm. Their rigorous presentation of this algorithm
 has mainly allowed them to prove two properties.
 The former states that if 
 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
@@ -55,7 +55,7 @@ exists a Gray code such that all transition count numbers
 are 2-powers whose exponents are either equal
 or differ from each other by 1.
 However, the authors do not prove that the approach allows to build 
-(totally balanced) Gray code. 
+(totally balanced) Gray codes. 
 What follows shows that this fact is established and first recalls the approach.
 
 
@@ -86,10 +86,10 @@ two elements have been exchanged.
 It has been proven in~\cite{ZanSup04} that 
 $S_{\mathsf{N}}$ is the transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
 if $S_{\mathsf{N}-2}$ is. 
-However, the step~(\ref{item:nondet}) is not a constructive 
-step that precises how to select the subsequences which ensures that 
+However, step~(\ref{item:nondet}) is not a constructive 
+step that precises how to select the subsequences which ensure that 
 yielded Gray code is balanced.
-Next section shows how to choose the sequence $l$ to have the balance property.
+Following sections show how to choose the sequence $l$ to have the balance property.
 
 \subsection{Balanced Codes}
 Let us first recall how to formalize the balance property of a Gray code.
@@ -118,14 +118,13 @@ the Hamiltonian cycle that has been removed in $f^*$.
 Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is 
 $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray code is balanced. 
 
-Let now  
-$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011,$ $0001, 0101,0100,$ $1100, 1101, 1001, 1011, 1010, 1000$
+Let  $L^4$ $=0000,0010,0110,1110,1111,0111,0011,0001,0101,0100,1100,1101,1001,1011,1010,1000$
 be a cyclic Gray code. Since $S=2,3,4,1,4,$ $3,2,3,1,4,1,3,2,1,2,4$, $\textit{TC}_4$ is equal to 4 everywhere, this code
 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  
-$L^{\textit{st}}=0000,0001,0011,$ 
-$0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000$,
+$L^{\textit{st}}=0000,0001,0011, 
+0010,0110,0111,0101,0100,$ \newline $1100,1101,1111,1110,1010,1011,1001,1000$,
 we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
 the code is neither balanced nor totally balanced.
 \end{xpl}
@@ -168,7 +167,7 @@ odd and even initial values.
 For the inductive case, let us first define some variables.
 Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements 
 whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
-These two variables are defined by the system 
+Both of these variables are defined by the system 
  
 \[
 \left\{
@@ -265,7 +264,7 @@ When $3 \le N \le 7$, values are defined as follows:
 \textit{TC}_{4} & = & [4,4,4,4] \\
 \textit{TC}_{6} & = & [10,10,10,10,12,12] \\
 \end{eqnarray*}
-It is not hard to verify that all these instanciations verify the aformentioned contraints. 
+It is not difficult to check that all these instanciations verify the aforementioned constraints. 
 
 When  $N  \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
 \begin{equation}