]> AND Private Git Repository - 16dcc.git/blobdiff - hamilton.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
modif abstract
[16dcc.git] / hamilton.tex
index ed7d21d3bc82f57d2518787ba3eb5305e154924f..b2c6e54f20363f788ccc99a530be58f74bbb40f2 100644 (file)
@@ -1,5 +1,5 @@
 Many approaches have been developed to solve the problem of building
 Many approaches have been developed to solve the problem of building
-a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 
+a Gray code in a $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 
 the produced code has to verify.
 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 
 the produced code has to verify.
 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 
@@ -16,13 +16,15 @@ and an algorithm that establishes locally balanced Gray codes is given.
  
 The current context is to provide a function 
 $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian 
  
 The current context is to provide a function 
 $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian 
-cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated
-$b$ time to produce a pseudo random number, \textit{i.e.} a vertex in the 
-$\mathsf{N}$ cube.
+cycle in the $\mathsf{N}$-cube. Such a function is going to be iterated
+$b$ times to produce a pseudo random number,
+\textit{i.e.} a vertex in the 
+$\mathsf{N}$-cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
-To reduced the number of iterations, the provided Gray code
-should ideally possess the both balanced and locally balanced properties.
+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:
 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}
 However, none of the two algorithms is compatible 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}
@@ -35,21 +37,21 @@ the number of switches of each element is as uniform as possible.
 \subsection{Analysis of the Robinson-Cohn extension algorithm}
 As far as we know three works, 
 namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96}, 
 \subsection{Analysis of the Robinson-Cohn extension algorithm}
 As far as we know three works, 
 namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96}, 
-and~\cite{ZanSup04} have adressed the probem of providing an approach
+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 
 a special subsequence of the transition sequence at each induction step.
 This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
 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 
 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 explicitely shown how to construct such a subsequence.
+where the authors have explicitly shown how to construct such a subsequence.
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
-algorithm. There rigourous presentation of this one 
+algorithm. There rigorous presentation of this one 
 have 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.
 The latter states that for every $\mathsf{N}$ there 
 have 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.
 The latter states that for every $\mathsf{N}$ there 
-exists a Gray code such that all transition count numbers are 
+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 
 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 
@@ -67,30 +69,30 @@ which produces a $n$-bits Gray code.
 $u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$ 
 such that $S_{\mathsf{N}-2}$ is the concatenation of 
 $$
 $u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$ 
 such that $S_{\mathsf{N}-2}$ is the concatenation of 
 $$
-s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
 $$
 where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
 $$
 where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
-\item Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
+\item\label{item:u'}Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
   by 
   $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
   respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that 
   $u^R$ is $u$ in reversed order. 
   The obtained sequence is further denoted as $U$.
   by 
   $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
   respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that 
   $u^R$ is $u$ in reversed order. 
   The obtained sequence is further denoted as $U$.
-\item Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first 
+\item\label{item:VW} Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first 
 two elements have been exchanged.
 \item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
 \end{enumerate} 
 
 It has been proven in~\cite{ZanSup04} that 
 two elements have been exchanged.
 \item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
 \end{enumerate} 
 
 It has been proven in~\cite{ZanSup04} that 
-$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
+$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 
 yielded Gray code is balanced.
 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 
 yielded Gray code is balanced.
-Next section shows how to choose the sequence $l$ to have the balancy property.
+Next section shows how to choose the sequence $l$ to have the balance property.
 
 \subsection{Balanced Codes}
 
 \subsection{Balanced Codes}
-Let us first recall how to formalize the balancy property of a Gray code.
+Let us first recall how to formalize the balance property of a Gray code.
 Let  $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence 
 of a $\mathsf{N}$-bits cyclic Gray code. 
 The  transition sequence 
 Let  $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence 
 of a $\mathsf{N}$-bits cyclic Gray code. 
 The  transition sequence 
@@ -111,15 +113,15 @@ $|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le  2$.
 
    
 \begin{xpl}
 
    
 \begin{xpl}
-Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to 
+Let $L^*=000,100,101,001,011,111,$ $110,010$ be the Gray code that corresponds to 
 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  
 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,$
+$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011,$ $0001, 0101,$
 $0100, 1100, 1101, 1001, 1011, 1010, 1000$
 $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
+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  
 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  
@@ -131,8 +133,8 @@ the code is neither balanced nor totally balanced.
 
 
 \begin{thrm}\label{prop:balanced}
 
 
 \begin{thrm}\label{prop:balanced}
-Let $\mathsf{N}$ in $\Nats$, and $a_{\mathsf{N}}$ be defined by
-$a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$. 
+Let $\mathsf{N}$ in $\Nats^*$, and $a_{\mathsf{N}}$ be defined by
+$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. 
 There exists then a sequence $l$ in 
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 
 There exists then a sequence $l$ in 
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 
@@ -144,7 +146,7 @@ for any $i$, $1 \le i \le \mathsf{N}$.
 
 
 
 
 
 
-The proof is done by induction on $\mathsf{N}$. Let us imadialty verify 
+The proof is done by induction on $\mathsf{N}$. Let us immediately verify 
 that it is established for both odd and even smallest values, \textit{i.e.} 
 $3$ and $4$.
 For the initial case where $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ we successively have:  $S_1=1,1$, $l=2$,  $u_0 = \emptyset$, and $v=\emptyset$.
 that it is established for both odd and even smallest values, \textit{i.e.} 
 $3$ and $4$.
 For the initial case where $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ we successively have:  $S_1=1,1$, $l=2$,  $u_0 = \emptyset$, and $v=\emptyset$.
@@ -166,33 +168,168 @@ 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 
 
 For the inductive case, let us first define some variables.
 Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements 
-whose transistion count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
+whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
 These two variables are defined by the system 
  
 These two variables are defined by the system 
  
-$$
+\[
 \left\{
 \begin{array}{lcl}
 c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
 c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}} 
 \end{array}
 \right.
 \left\{
 \begin{array}{lcl}
 c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
 c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}} 
 \end{array}
 \right.
-\qquad 
 \Leftrightarrow 
 \Leftrightarrow 
-\qquad 
 \left\{
 \begin{array}{lcl}
 \left\{
 \begin{array}{lcl}
-d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N} -n.a_{\mathsf{N}}}{2} \\
-c_{\mathsf{N}} = \mathsf{N} -  d_{\mathsf{N}}
+d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
+c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
+\end{array}
+\right.
+\]
+
+Since $a_{\mathsf{N}}$ is even, $d_{\mathsf{N}}$ is an integer.
+Let us first proove that both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are positive
+integers.
+Let $q_{\mathsf{N}}$ and $r_{\mathsf{N}}$, respectively, be  
+the quotient and the remainder in the Euclidean disvision
+of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.} 
+$2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, with $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
+First of all, the integer $r$ is even since $r_{\mathsf{N}} = 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$. 
+Next,  $a_{\mathsf{N}}$ is $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Consequently 
+$d_{\mathsf{N}}$ is $r_{\mathsf{N}}/2$ and is thus a positive integer s.t. 
+$0 \le d_{\mathsf{N}} <\mathsf{N}$.
+The proof for $c_{\mathsf{N}}$ is obvious.
+
+
+For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$) 
+be the occurence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$ 
+(resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$)
+in step (\ref{item:nondet}) of the algorithm.
+
+Due to the definition of $u'$ in step~(\ref{item:u'}), 
+$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ is the
+ number of element $i$ in the sequence $U$.
+It is clear that the number of element $i$ in the sequence $V$ is 
+$2bi_{\mathsf{N}}$ due to step (\ref{item:VW}). 
+We thus have the following system:
+$$
+\left\{
+\begin{array}{lcl}
+3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\
+zi_{\mathsf{N}} + ti_{\mathsf{N}}  + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i)
 \end{array}
 \right.
 \end{array}
 \right.
+\qquad 
+\Leftrightarrow 
 $$
 
 $$
 
-Since $a_{\mathsf{N}$ is even, $d_{\mathsf{N}}$ is defined.
-Both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are obviously positves.
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= & 
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt1}
+\end{equation}
+
+In this set of 2 equations with 3 unknown variables, let $b_i$ be set with 0.
+In this case, since $\textit{TC}_{\mathsf{N}}$ is even (equal to $a_{\mathsf{N}}$ 
+or to $a_{\mathsf{N}}+2$), the variable  $zi_{\mathsf{N}}$ is thus an integer.
+Let us now prove that the resulting system has always positive integer 
+solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ 
+and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$. 
+This latter consraint is obviously established if the system has a solution.
+We thus have the following system.
+
+
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= & 
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt2}
+\end{equation}
+
+The definition of $\textit{TC}_{\mathsf{N}}(i)$ depends on the value of $\mathsf{N}$.
+When $3 \le N \le 7$, values are defined as follows:
+\begin{eqnarray*}
+\textit{TC}_{3} & = & [2,2,4] \\
+\textit{TC}_{5} & = & [6,6,8,6,6] \\
+\textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\
+\\
+\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. 
+
+When  $N  \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
+\begin{equation}
+\textit{TC}_{\mathsf{N}}(i) = \left\{
+\begin{array}{l} 
+a_{\mathsf{N}} \textrm{ if } 1 \le i \le c_{\mathsf{N}} \\
+a_{\mathsf{N}}+2 \textrm{ if } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}} 
+\end{array}
+\right.
+\label{eq:TCN:def}
+\end{equation}
+
+
+We thus  have
+\[
+\begin{array}{rcl} 
+\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) 
+&\ge& 
+a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
+&\ge& 
+\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\ge& 
+\frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\ge& 
+\frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
+\end{array}
+\]
+
+A simple variation study of the function $t:\R \rightarrow \R$ such that 
+$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that 
+its derivative is strictly postive if $x \ge 6$ and $t(8)=224$.
+The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive 
+for any $\mathsf{N} \ge 8$ and the proof is established.
+
+
+% \begin{table}[ht]
+% $$
+% \begin{array}{|l|l|l|l|l|l|}
+% \hline
+% \mathsf{N}     & 3 & 4 & 5 & 6  & 7\\
+% \hline
+% a_{\mathsf{N}} & 2 & 4 & 6 & 10 & 18\\
+% \hline
+% \end{array}
+% $$
+% \label{tab:an}
+% \caption{First values of  $a_{\mathsf{N}}$}
+% \end{table}
 
 
+For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions 
+among $\textit{TC}_{\mathsf{N}}(i)$, which leads to 
+${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities.
+Notice that all such choices lead to a hamiltonian path.
 
 
 
 
 
 
 
 
 
 
-\subsection{Toward a local uniform distribution of switches}
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End: