text:
\section{Introduction}

\IEEEPARstart{S}{hift and timing} errors are a dominant type of noise in several
communication and information storage scenarios, examples of which include magnetic
and optical recording devices \cite{hilden, shamai+zehavi},
inductively coupled channels such as the reader-to-tag RFID channel \cite{rosnes},
parallel asynchronous communications \cite{engelberg+keren},
various types of timing channels \cite{anantharam+verdu, kovacevic+popovski, nakano}, etc.
Designing codes that are able to correct these types of errors and studying their
fundamental limits is important for all these applications, in addition to being
an interesting theoretical challenge.
The problem is further complicated by the fact that, in many of the mentioned
applications, particularly magnetic, optical, and emerging DNA storage systems,
the codewords are required to satisfy modulation constraints that are introduced to
alleviate inter-symbol interference and other impairing effects
\cite{immink, immink1, immink2, immink+cai, siegel, siegel+wolf}.
Perhaps the best-known example of such constraints are runlength constraints where
a minimum and a maximum number of zero symbols between two consecutive non-zero
symbols is specified.
Motivated by these communication settings, we study the error correction problem
for channels with shift and timing errors, and with runlength input constraints.
The precise channel model we have in mind and our contributions are described in the
following two subsections.

\subsection{The Channel Model}
\label{sec:model}

Fix $ d, k \in \mathbb{Z} \cup \{\infty\} $ with $ 0 \leq d < k \leq \infty $.
We assume that the channel inputs are binary strings of length $ n $ that are
composed of blocks from the set $ \{0^d 1, \ldots, 0^k 1\} $, where $ 0^j $
is a string of $ j $ zeros.
In other words, the set of inputs is
\begin{equation}
\label{eq:dk}
  \myS_{d,k}(n) \defeq \big\{0, 1\big\}^n \cap \big\{0^d 1, \ldots, 0^k 1\big\}^* .
\end{equation}
(Here $ A^* $ is the usual notation for the set $ \bigcup_{i=0}^\infty A^i $.)
For a string $ \myx = x_1 \cdots x_n \in \{0, 1\}^n $, denote by
$ \weight(\myx) = \sum_{i=1}^n x_i $ its Hamming weight.
It will be convenient to introduce a special notation for the set of all channel
inputs of a given weight $ W $:
\begin{equation}
\label{eq:dkW}
  \myS_{d,k}(n, W) \defeq \Big\{ \myx \in \myS_{d,k}(n) : \weight(\myx) = W \Big\} .
\end{equation}
In other words, $ \myS_{d,k}(n, W) $ contains all those input strings that are
composed of exactly $ W $ blocks from the set $ \{0^d 1, \ldots, 0^k 1\} $.

The definition \eqref{eq:dk} ensures that
\begin{inparaenum}
\item[(a)]
consecutive $ 1 $'s in any input string are separated by at least $ d $ and at
most $ k $ zeros, and
\item[(b)]
every input string starts with a string of zeros of length
$ j $, $ d \leq j \leq k $, and ends with a $ 1 $.
\end{inparaenum}
The property (a) is the defining property of the so-called $ (d,k) $-constrained
sequences.
However, the boundary conditions (b) are not universally adopted in the literature
\cite{immink}.
We shall nevertheless find it convenient to work under definition \eqref{eq:dk}, as
in, e.g., \cite{krachkovsky};
it will be evident later on that different boundary conditions would not affect the
analysis in any significant way.

For a given input string $ \myx \in \myS_{d,k}(n,W) $, the channel outputs another
binary string $ \myy $ of length $ n $ and weight $ W $.\linebreak
We think of $ 1 $'s in $ \myx $ as being ``shifted'' in the channel, each for a number
of positions to the left or to the right of its original position, thus producing
$ \myy $ at the output.
We say that $ t $ bit-shifts have occurred in the channel if
$ \sum_{i=1}^W |\bar{x}_i - \bar{y}_i| = t $, where $ \bar{x}_i $ (resp. $ \bar{y}_i $)
is the position of the $ i $'th $ 1 $ in $ \myx $ (resp. $ \myy $), $ 1 \leq i \leq W $;
see Example \ref{exmpl} for an illustration.

\begin{example}
\label{exmpl}
\textnormal{
Consider an input string $ \myx \in \myS_{2,4}(15,4) $ and the corresponding
output string $ \myy $:
\begin{equation}
\label{eq:xyshift}
\begin{aligned}
  \myx \ &= \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 1   \\
  \myy \ &= \ 0 \ 1 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 1 .
\end{aligned}
\end{equation}
We think of $ \myy $ as obtained from $ \myx $ by shifting the first $ 1 $
in $ \myx $ one position to the left, the second $ 1 $ two positions to the left,
and the third $ 1 $ one position to the right.
We then say that the total number of bit-shifts that occurred in the channel is
$ t = 1 + 2 + 1 = 4 $.
\myqed
}
\end{example}

Note that the output string $ \myy $ may in general violate the $ (d,k) $-constraints.

\subsection{Main Results}

Our main object of study in the present paper are error-correcting codes for
the above-described channel model.
In particular, we shall derive explicit bounds on the cardinality of optimal
$ (d, k) $-constrained codes correcting $ t $ shifts, with a focus on their
asymptotic behavior in the regime of growing block-length ($ n \to \infty $).
Despite a sizable body of literature on the bit-shift channel and related models%
\footnote{See, e.g., \cite{abdelghaffar+weber, bours, ferreira+lin, hilden, klove2,
kolesnik+krachkovsky, kuznetsov+hanvinck, levenshtein+hanvinck, rosnes, roth+siegel,
shamai+zehavi, ytrehus, ytrehus2}.},
such bounds, to the best of our knowledge, have not been obtained before%
\footnote{The only bounds appearing in the literature that we are aware of
are those in \cite{abdelghaffar+weber} (and \cite{ytrehus} for $ t = 1 $)
for the symmetric case; see Section \ref{sec:main_d1} ahead.
However, these bounds are not explicit and are difficult to compare to ours.
We also mention here the work \cite{kolesnik+krachkovsky}, where a lower bound
was obtained for a different asymptotic regime where $ t $ grows with $ n $,
and \cite{krachkovsky}, where bounds on codes correcting \emph{all} bit-shift
errors of maximum magnitude $ s $ (zero-error codes) were derived and shown
to be tight in some cases.}
, even for a single bit-shift ($ t = 1 $).

We consider two scenarios.
The first one, analyzed in Section \ref{sec:main_da}, corresponds to the situation
where right-shifts and left-shifts are treated independently, and separate
requirements on their correctability are imposed.
More precisely, codes are in this case required to have the capability of correcting
$ \tright $ right-shifts and $ \tleft $ left-shifts, for given $ \tright $ and $ \tleft $.
The second scenario, analyzed in Section \ref{sec:main_d1}, corresponds to the
situation where right-shifts and left-shifts are treated in a symmetric way, i.e.,
where codes are required to have the capability of correcting $ t $ shifts, regardless
of the direction of each individual shift.
In both cases, the appropriate metric is given that describes the error-correcting
capability of a code.

In Section \ref{sec:space} we state several properties of the code space
$ \myS_{d,k}(n) $ that are needed to derive the bounds in Sections \ref{sec:main_da}
and \ref{sec:main_d1} but are also of possible interest in other settings.
In particular, we determine the capacity of the noiseless channel with
$ (d, k) $-constrained \emph{constant-weight} inputs, i.e., the exponential
growth-rate of $ |\myS_{d,k}(n,wn)| $ as $ n \to \infty $.
To the best of our knowledge this quantity has not been characterized before,
even though enumeration and encoding/decoding algorithms for constant-weight
$ (d, k) $-constrained sequences have been studied in several works \cite{kurmaev2, kurmaev}.

\subsection{Notation}

$ \log $ denotes the base-$ 2 $ logarithm.

If we write $ \sum_i s_i $, it is understood that $ i $ ranges over all
possible values, which will be clear from the context.

We adopt the following asymptotic notation: for any two non-negative real
sequences $ (a_n) $ and $ (b_n) $,
\begin{itemize}
\item
$ a_n \sim b_n $ means $ \lim_{n \to \infty} \frac{a_n}{b_n} = 1 $;
\item
$ a_n \gtrsim b_n $ means $ \liminf_{n \to \infty} \frac{a_n}{b_n} \geq 1 $;
\item
$ a_n \simexp b_n $ means $ \log a_n  \sim  \log b_n $
(i.e., the \emph{exponents} of $ a_n $ and $ b_n $ have the same asymptotic behavior);
\item
$ a_n = {\mathcal O}(b_n) $ means $ \limsup_{n \to \infty} \frac{a_n}{b_n} < \infty $;
\item
$ a_n = o(b_n) $ means $ \lim_{n \to \infty} \frac{a_n}{b_n} = 0 $.
\end{itemize}

\section{The Code Space}
\label{sec:space}

In this section we demonstrate some properties of the set $ \myS_{d,k}(n) $
that will be used in the derivations to follow but are also of potential interest
in other applications.
We also describe another representation of this space that is of course equivalent
to the one given in \eqref{eq:dk}--\eqref{eq:dkW} but that may be preferable to it,
depending on the problem being analyzed.

\subsection{Equivalent Representation}
\label{sec:representation}

Another representation of the set of all channel inputs that is useful for analyzing
bit-shift errors is based on specifying the positions of $ 1 $'s in the input string
\cite{abdelghaffar+weber}.

For $ \myx \in \myS_{d,k}(n,W) $, we denote by $ \myxx = (\bar{x}_1, \ldots, \bar{x}_W) $
the vector indicating the positions of $ 1 $'s in the string $ \myx $, meaning that
$ \bar{x}_i $ is the position of the $ i $'th $ 1 $ in $ \myx $.
For example, for $ {\myx = 0 1 0 0 1 0 1 \in \myS_{1,3}(7,3)} $ we have $ \myxx = (2, 5, 7) $.
The mapping $ \myx \mapsto \myxx $ is clearly one-to-one.
With this correspondence in mind, we define
\begin{align}
\label{eq:space}
\nonumber
  \mySS_{d,k}(&n, W) \defeq  \Big\{ \myxx \in \mathbb{Z}^W  : 0 < \bar{x}_1 < \cdots < \bar{x}_W = n,   \\
  &d + 1 \leq \bar{x}_{i} - \bar{x}_{i-1} \leq k + 1  \;\; \text{for} \;\; i = 1, \ldots, W \Big\} ,
\end{align}
where we understand that $ \bar{x}_0 = 0 $.
Hence, $ \mySS_{d,k}(n, W) $ is just a different representation of the set of
all channel inputs of length $ n $ and weight $ W $, namely $ \myS_{d,k}(n, W) $,
and $ \mySS_{d,k}(n) \defeq \bigcup_{W} \mySS_{d,k}(n, W) $ is the corresponding
representation of the set of all channel inputs of length $ n $, namely $ \myS_{d,k}(n) $.
Note that $ \mySS_{d,k}(n, W) $ is a $ (W-1) $-dimensional subset of $ \mathbb{Z}^W $
because the position of the last $ 1 $ in every input string is fixed to $ n $ by
our convention \eqref{eq:dk}, i.e.,
\begin{equation}
\label{eq:dimW-1}
  \mySS_{d,k}(n)  \subset \mathbb{Z}^{W-1}\!\times\!\{n\} .
\end{equation}

The space $ \mySS_{d,k}(n) $, or $ \mySS_{d,k}(n, W) $ in the constant-weight
case, seems to be more convenient for describing constructions of codes for the
bit-shift channel.

\subsection{Combinatorial Description and Asymptotics}

Define
\begin{subequations}
\begin{alignat}{3}
  &S_{d,k}(n)    && \defeq  | \myS_{d,k}(n) |    && = | \mySS_{d,k}(n) | ,  \\
  &S_{d,k}(n,W)  && \defeq  | \myS_{d,k}(n, W) | && = | \mySS_{d,k}(n, W) | ,
\end{alignat}
\end{subequations}
and note that
\begin{equation}
\label{eq:Wdecomp}
  S_{d,k}(n) = \sum_{W=0}^n S_{d,k}(n, W) .
\end{equation}
We see from the definition of the code space \eqref{eq:dk} that $ S_{d,k}(n) $
is in fact the number of \emph{compositions}%
\footnote{A composition of an integer $ n $ is a tuple of positive integers (called
parts) summing to $ n $ \cite{stanley}.
For a study of compositions with parts restricted to a subset of $ \mathbb{N} $
see, e.g., \cite{heubach+mansour}.}
of the integer $ n $ with parts restricted to the set $ \{d+1, \ldots, k+1\} $.
This number can be expressed in the recursive form
\begin{equation}
\label{eq:Sdkrec}
  S_{d,k}(n) = \sum_{i=d+1}^{k+1}  S_{d,k}(n-i)
\end{equation}
with initial conditions $ S_{d,k}(0) = 1 $ and $ S_{d,k}(n) = 0 $ for $ n < 0 $.
As is well-known \cite{tang+bahl}, this implies that $ S_{d,k}(n) \sim c \rho^{- n} $,
where $ \rho $ is the unique positive solution%
\footnote{That the positive solution is unique can be seen from the fact that
the function $ \sum_{i=d+1}^{k+1}  x^{i} $ is monotonically increasing from zero
to infinity over the half-line $ x \geq 0 $.
It is also easy to see that the solution lies in the range $ (0,1) $.}
to the characteristic equation $ \sum_{i=d+1}^{k+1}  x^{i} = 1 $, and the constant
$ c $ can be obtained from the recurrence \eqref{eq:Sdkrec} and its initial conditions.

Similarly, $ S_{d,k}(n,W) $ is the number of compositions of the integer $ n $
having exactly $ W $ parts, each part belonging to the set $ \{d+1, \ldots, k+1\} $.
This quantity can be expressed in the recursive form \cite{heubach+mansour}:
\begin{equation}
\label{eq:SdkWrec}
  S_{d,k}(n, W) = \sum_{i=d+1}^{k+1}  S_{d,k}(n-i, W-1)
\end{equation}
with initial conditions $ S_{d,k}(0, 0) = 1 $, $ S_{d,k}(n, 0) = 0 $ for $ n \neq 0 $,
and $ S_{d,k}(n, W) = 0 $ for $ n < 0 $.
For $ k = \infty $ we can obtain an explicit solution to \eqref{eq:SdkWrec}
by directly counting the compositions of $ n $ with parts in $ \{d+1, d+2, \ldots\} $:
\begin{equation}
\label{eq:SdkWrecursive1}
  S_{d,\infty}(n, W) = \binom{ n - 1 - Wd }{ W - 1 } .
\end{equation}
In particular, $ S_{0,\infty}(n, W) = \binom{ n - 1 }{ W - 1 } $ and
$ S_{0,\infty}(n) = 2^{n-1} $ (recall that the last bit of every sequence is
fixed to $ 1 $ by our convention \eqref{eq:dk}).
In the following lemma we characterize the asymptotic behavior of $ S_{d,k}(n, W) $
as $ n \to \infty $ and $ {W = w n} $, for fixed
$ w \in \big[ \frac{1}{k+1}, \frac{1}{d+1} \big] $.
For simplicity, we write $ w n $ instead of, e.g., $ \floor{w n} $,
ignoring the fact that the former is not necessarily an integer.

For $ w \in \big( \frac{1}{k+1}, \frac{1}{d+1} \big) $ define the function
\begin{equation}
\label{eq:sigma}
  \sigma_{d,k}(w)  \defeq  w \log\!\sum_{i=d+1}^{k+1} \rho_w^{i-\frac{1}{w}} ,
\end{equation}
where $ \rho_w $ is the unique positive solution to
$ \sum_{i=d+1}^{k+1} (w i - 1) x^{i} = 0 $.
Additionally, let $ \sigma_{d,k}\big(\frac{1}{k+1}\big) = \sigma_{d,k}\big(\frac{1}{d+1}\big) = 0 $.

\begin{lemma}
\label{thm:expW}
\begin{itemize}
\item[(a)]
For any fixed $ w \in \big[ \frac{1}{k+1}, \frac{1}{d+1} \big] $ we have
\begin{equation}
\label{eq:expW}
  \lim_{n \to \infty} \frac{1}{n} \log S_{d,k}(n, wn)  =  \sigma_{d,k}(w) .
\end{equation}
\item[(b)]
The exponent $ \sigma_{d,k}(w) $ is a continuous, strictly concave function of $ w $.
It attains its maximal value at
\begin{equation}
  w^* = \left(\sum_{i=d+1}^{k+1} i \rho^{i} \right)^{-1}
\end{equation}
and this value is $ \sigma_{d,k}(w^*) = - \log \rho $,
where $ \rho $ is the unique positive solution to $ \sum_{i=d+1}^{k+1}  x^{i} = 1 $.
\end{itemize}
\end{lemma}

\begin{IEEEproof}
  The part \emph{(a)} of the claim referring to the asymptotics of
$ S_{d,k}(n, wn) $ as $ n \to \infty $ follows from the known results in
analytic combinatorics \cite{pemantle+wilson}.
Namely, the generating function of the bivariate sequence $ (S_{d,k}(n, W))_{n,W} $
is obtained from \eqref{eq:SdkWrec} as:
\begin{equation}
\label{eq:gen}
\begin{aligned}
  F_{d,k}(x,y)  \defeq  \phantom{}
	                  &\sum_{n=0}^{\infty} \sum_{W=0}^{\infty}  S_{d,k}(n, W) x^n y^W  \\
                =       \phantom{}
						        &\frac{1}{1 - y (x^{d+1} + \cdots + x^{k+1})} ,
\end{aligned}
\end{equation}
wherefrom one verifies that this sequence is a Riordan array%
\footnote{Bivariate sequences with generating functions of the form $ \frac{\phi(x)}{1 - y v(x)} $
are called (generalized) Riordan arrays; see \cite[Sec.\ 12.2]{pemantle+wilson}.}
and satisfies the conditions of \cite[Thm 12.2.2]{pemantle+wilson}.
We then conclude from \cite[Thm 12.2.2]{pemantle+wilson} that
\begin{equation}
\label{eq:expW2}
  S_{d,k}(n, wn)  \simexp  v(\rho_w)^{w n} \rho_w^{-n}
                  =       \left(\sum_{i=d+1}^{k+1}  \rho_w^{i-\frac{1}{w}} \right)^{w n} ,
\end{equation}
where $ v(x) \defeq \sum_{i=d+1}^{k+1} x^i $ is the polynomial appearing
in the denominator of the generating function \eqref{eq:gen}, and $ \rho_w $
is the unique positive solution to $ \frac{x \deriv{x} v(x)}{v(x)} = \frac{1}{w} $.
This proves \eqref{eq:expW}.

The part \emph{(b)} of the claim is obtained by carefully analyzing the involved
functions.
The root $ \rho_w $ is a function of the relative weight $ w $ and is implicitly
defined by $ \sum_{i=d+1}^{k+1} (w i - 1) \rho_w^{i} = 0 $,  $ \rho_w > 0 $.
Differentiating this equation w.r.t.\ $ w $ we find that $ \deriv{w} \rho_w < 0 $.
Also, we have
$ \deriv{w} \sigma_{d,k}(w) = \log \sum_{i=d+1}^{k+1} \rho_w^{i} $
and $ \dderiv{w} \sigma_{d,k}(w) = \log e \cdot \frac{\deriv{w} \rho_w}{w \rho_w} < 0 $,
implying that $ \sigma_{d,k}(w) $ is concave.
The weight $ w^* $ that maximizes the exponent $ \sigma_{d,k}(w) $ is the one
for which $ \deriv{w} \sigma_{d,k}(w) = 0 $, i.e.,
$ v(\rho_w) = \sum_{i=d+1}^{k+1} \rho_w^{i} = 1 $.
\end{IEEEproof}
\vspace{2mm}

It is illustrative to specialize Lemma 1 to $ k = \infty $ because this case
admits an explicit solution.
After a simple calculation we get $ \rho_w = \frac{1-w(d+1)}{1-wd} $ and
\begin{equation}
\label{eq:expkinfty}
  \sigma_{d,\infty}(w) = (1 - w d) H\Big(\frac{w}{1 - w d}\Big) ,
\end{equation}
where $ H(\cdot) $ is the binary entropy function, which can also be found
directly from \eqref{eq:SdkWrecursive1} by using Stirling's approximation.
The exponent \eqref{eq:expkinfty} is maximized at $ w^* = \frac{1-\rho}{1+(1-\rho)d} $,
where $ \rho $ is the unique positive solution to $ 1 - x - x^{d+1} = 0 $.
Further specializing to $ d = 0 $, we recover the well-known fact that
$ \sigma_{0,\infty}(w) = H(w) $, in which case $ \rho = 1/2 $ and $ w^* = 1/2 $.

The quantity $ \sigma_{d,k}(w) $ defined in \eqref{eq:sigma} is the maximal
information rate (i.e., the capacity) that can be achieved in the \emph{noiseless}
channel with $ (d, k) $-constrained inputs of relative weight $ w $.
This is a refinement of the well-known result that states that the capacity of
the noiseless channel with $ (d, k) $-constrained inputs (but with \emph{no} weight
constraints) is $ \lim_{n \to \infty} \frac{1}{n} \log S_{d,k}(n) = - \log \rho $
\cite{tang+bahl}.
Namely, it follows from \eqref{eq:Wdecomp} and the fact that the exponential
growth-rate of $ S_{d,k}(n,w n) $ is maximized for $ w = w^* $ (Lemma~\ref{thm:expW})
that
$ S_{d,k}(n) \simexp S_{d,k}(n,w^* n) \simexp 2^{n \sigma_{d,k}(w^*)} = 2^{- n \log \rho} $.
The following claim strengthens this result; it asserts that the input strings of
weight (approximately) equal to $ w^* n $ account for most of the space $ \myS_{d,k}(n) $.
Informally, we say that the ``typical''%
\footnote{Lemmas \ref{thm:typicalw} and \ref{thm:typicaldk} can also be expressed
in the probabilistic language. Such a formulation is close in spirit to the statements
about high-probability sets and typical sequences in information theory \cite{cover+thomas}.}
{$ (d,k) $-constrained} strings have relative weight $ w^* $.

\begin{lemma}
\label{thm:typicalw}
  There exists a sublinear function%
\footnote{The function $ f $ may depend on the parameters $ d, k $ as well;
this is suppressed for notational simplicity.}
$ f(n) = o(n) $ such that, as $ n \to \infty $,
\begin{equation}
\label{eq:CWasymp2}
  \sum_{W \,:\, |W - w^*n| > f(n)} S_{d,k}(n, W)
    \;\lesssim\;   \frac{S_{d,k}(n)}{n^{\log n}} .
\end{equation}
\end{lemma}
\begin{IEEEproof}
  Recall that
\begin{inparaenum}
\item[(a)]
$ S_{d,k}(n) $ grows exponentially with exponent $ - \log \rho $,
\item[(b)]
$ S_{d,k}(n, W) $ grows exponentially with exponent $ \sigma_{d,k}(w) $ that
is uniquely maximized at $ w^* $, and
\item[(c)]
there are only linearly (in $ n $) many possible weights $ W $ (see \eqref{eq:Wdecomp}).
\end{inparaenum}
These facts together imply that, for any given $ \epsilon > 0 $, the number
of $ (d,k) $-constrained strings of weight $ W $ satisfying $ |W - w^* n| > \epsilon n $
is exponential with an exponent \emph{strictly smaller} than $ -\log \rho $.
More precisely, for every $ \epsilon > 0 $ there exists a (sufficiently small)
$ \gamma(\epsilon) > 0 $ such that, as $ n \to \infty $,
\begin{align}
\label{eq:CWasymp3}
  \sum_{W \,:\, |W - w^*n| > \epsilon n} S_{d,k}(n, W)
	  \;\lesssim\;   \frac{S_{d,k}(n)}{2^{\gamma(\epsilon) n}} .
\end{align}
This further implies that, for every $ \epsilon > 0 $ and large enough $ n $,
\begin{align}
\label{eq:CWasymp4}
	  \sum_{W \,:\, |W - w^*n| > \epsilon n} S_{d,k}(n, W)   \;<\;   \frac{S_{d,k}(n)}{n^{\log n}} .
\end{align}
Let $ n_0(\epsilon) $ be the smallest positive integer such that \eqref{eq:CWasymp4}
holds for all $ n \geq n_0(\epsilon) $.
Take an arbitrary sequence $ (\epsilon_i) $ satisfying
$ 1 = \epsilon_0 > \epsilon_1 > \epsilon_2 > \ldots $ and $ \lim_{i \to \infty} \epsilon_i = 0 $,
and define the function:
\begin{equation}
\label{eq:f}
  f(n)  \defeq  \epsilon_i n ,  \qquad   n_0(\epsilon_i) \leq n < n_0(\epsilon_{i+1}) .
\end{equation}
It is now easy to verify that \eqref{eq:CWasymp4} and \eqref{eq:f} imply
\eqref{eq:CWasymp2}.
\end{IEEEproof}
\vspace{2mm}

The function $ n^{\log n} $ in the statement of Lemma \ref{thm:typicalw} can
be replaced with an arbitrary sub-exponential function, but this choice is
sufficient for our purposes.
In particular, since
$ \frac{\rho^{-n}}{n^{\log n}} = o\big(\frac{\rho^{-n}}{n^t}\big) $
for any fixed $ t $, Lemma \ref{thm:typicalw} implies that one can, without
loss of generality, disregard the non-typical input strings in the asymptotic
analysis of optimal codes correcting $ t $ shifts.

In the sequel, we shall also need an estimate of the number of blocks $ 0^j 1 $,
for fixed $ j \in \{d, \ldots, k\} $, in typical input strings.
For the purpose of formally stating this result, denote by
$ S_{d,k}^{(j)}(n, W, \ell) $ the number of input strings consisting of $ W $
blocks from $ \{0^d 1, \ldots, 0^k 1\} $, exactly $ \ell $ of which are $ 0^j 1 $.
Equivalently, $ S_{d,k}^{(j)}(n, W, \ell) $ is the number of compositions of
the number $ n $ with $ W $ parts, the parts taking values in $ \{d+1, \ldots, k+1\} $,
and exactly $ \ell $ of them having value $ j + 1 $.
We then have $ S_{d,k}(n,W)  =  \sum_{\ell=0}^W  S_{d,k}^{(j)}(n, W, \ell) $,
for every $ j \in \{d, \ldots, k\} $.

\begin{lemma}
\label{thm:typicaldk}
  Fix $ j \in \{d, \ldots, k\} $ and denote
$ \lambda_j^* \defeq \rho^{j+1} w^*
              =      \rho^{j+1} \big(\sum_{i=d+1}^{k+1} i \rho^{i} \big)^{-1} $,
where $ \rho $ is the unique positive solution to $ \sum_{i=d+1}^{k+1}  x^{i} = 1 $.
Then, for every $ j \in \{d, \ldots, k\} $, as $ n \to \infty $ we have
\begin{equation}
\label{eq:expruns}
  S_{d,k}(n)  \simexp  S_{d,k}^{(j)}\big(n, w^*n, \lambda_j^* n\big) .
\end{equation}
Moreover, there exists a sublinear function $ f(n) = o(n) $ such that,
for every $ j \in \{d, \ldots, k\} $, as $ n \to \infty $ we have
\begin{equation}
\label{eq:runs}
  S_{d,k}(n) -
   \sum_{\substack{W, \ell \, : \, |W - w^* n| \leq f(n) , \\ \hskip 8mm |\ell - \lambda_j^* n| \leq f(n)}}
     S_{d,k}^{(j)}(n, W, \ell)
			\;\lesssim\;   \frac{S_{d,k}(n)}{n^{\log n}} .
\end{equation}
\end{lemma}

\begin{IEEEproof}
  Let us consider $ j = d $ and denote $ \lambda \defeq \lambda_d $ for simplicity;
the proof for general $ j $ is analogous.
The following relation is valid:
\begin{equation}
\label{eq:Sdkl}
  S_{d,k}^{(d)}(n, W, \ell)  =  \binom{W}{\ell}  S_{d+1,k}\big(n-\ell(d+1), W-\ell\big)
\end{equation}
(the $ \ell $ parts of value $ d+1 $ can be distributed among the $ W $ parts in
$ \binom{W}{\ell} $ ways, and the remaining $ W - \ell $ parts, which are all from
$ \{d+2, \ldots, k+1\} $, form a composition of the number $ n - \ell (d + 1) $),
and therefore
\begin{equation}
\label{eq:SdknWj}
  S_{d,k}(n)  =  \sum_W \sum_{\ell} \binom{W}{\ell} S_{d+1,k}\big(n-\ell(d+1), W-\ell\big) .
\end{equation}
Since the sum in \eqref{eq:SdknWj} has polynomially many terms, we know that it
grows exponentially with the same exponent as one of its summands $ W = w n $,
$ \ell = \lambda n $, for some $ w \in \big(\frac{1}{k+1}, \frac{1}{d+1}\big) $
and $ \lambda \in (0,w) $.
By using Stirling's approximation and \eqref{eq:expW}, this exponent can be
expressed in the form
\begin{subequations}
\begin{equation}
\label{eq:expWj}
\begin{aligned}
  \lim_{n \to \infty}  &\frac{1}{n} \log\!\Bigg[ \binom{w n}{\lambda n}  S_{d+1,k}\big(n - \lambda n (d+1), (w - \lambda) n\big) \Bigg]   \\
	 &= \;  w H\Big(\frac{\lambda}{w}\Big) + (w - \lambda) \log \sum_{i=d+2}^{k+1}  \rho_{w,\lambda}^{i - \frac{1-\lambda(d+1)}{w - \lambda}}  ,
\end{aligned}
\end{equation}
where $ H(\cdot) $ is the binary entropy function and $ \rho_{w,\lambda} > 0 $
is a function implicitly defined by
\begin{equation}
  \sum_{i=d+2}^{k+1}  \left(i - \frac{1-\lambda(d+1)}{w - \lambda}\right) \rho_{w,\lambda}^i = 0  .
\end{equation}
\end{subequations}
By calculating the derivatives of the exponent (the function on the right-hand
side of \eqref{eq:expWj}) with respect to $ w $ and $ \lambda $, one finds
that it is \emph{uniquely} maximized for $ \lambda^* = \rho^{d+1} w^* $,
$ w^* = \big( \sum_{i=d+1}^{k+1} i \rho^i \big)^{-1} $, where
$ \sum_{i=d+1}^{k+1} \rho^i = 1 $.
This implies that
\begin{equation}
\label{eq:}
  S_{d,k}(n)  \simexp  S_{d,k}^{(d)}\big(n, w^*n, \lambda^* n\big)
\end{equation}
and proves \eqref{eq:expruns}.
It also implies that, for \emph{every} $ \epsilon > 0 $, the part of the sum in
\eqref{eq:SdknWj}
where $ W \leq (w^* - \epsilon) n $ \emph{or} $ W \geq (w^* + \epsilon) n $ \emph{or}
$ \ell \leq (\lambda^* - \epsilon) n $ \emph{or} $ \ell \geq (\lambda^* + \epsilon) n $
is exponentially smaller than the remaining part, from which we infer \eqref{eq:runs}
by a reasoning identical to that in the proof of Lemma \ref{thm:typicalw}
(see \eqref{eq:CWasymp3}--\eqref{eq:f}).
\end{IEEEproof}
\vspace{2mm}

In words, $ (d,k) $-constrained strings of length $ n $ typically contain
$ \sim \lambda_j^* n $ blocks $ 0^j 1 $, i.e., runs of zeros%
\footnote{A run of zeros is a block of contiguous zeros of maximal length, i.e.,
such that it is delimited on both sides either by a $ 1 $, or by the end of the
string.}
of length $ j $, and all the non-typical strings can be safely ignored in the
asymptotic analysis.
Notice that, since $ \sum_{i=d+1}^{k+1} \rho^i = 1 $, we have
$ \sum_{j=d}^k \lambda_j^* = w^* $, which is expected as $ w^* n $ is the
total (typical) number of blocks in the input strings of length $ n $.

For example, in the unconstrained case ($ d = 0, k = \infty $) we have
$ \rho = 1/2 $, $ w^* = 1/2 $, and $ \lambda_j^* = 2^{-(j+2)} $ for $ j \geq 0 $.
As a further illustration, numerical values of the quantities discussed in Lemmas
\ref{thm:expW} and \ref{thm:typicaldk} are listed in Table \ref{tab:typical}
for several archetypal $ (d,k) $-constraints;
see, e.g., \cite{immink, immink2, siegel+wolf} for applications of these
and other $ (d,k) $-constrained codes.

{
\renewcommand{\arraystretch}{1.3}
\begin{table}[h]
\centering
\caption{The exponential growth-rate of the number of $ (d,k) $-constrained
         strings ($ -\log\rho $), and the typical values of the relative
				 Hamming weight ($ w^* $) and the relative numbers of runs of zeros
				 of length $ j $ ($ \lambda_j^* $) in $ (d,k) $-constrained strings
         of length $ n \to \infty $ (rounded to three decimal places).}
 \begin{tabular}{ | c || c | c | c | c | c | }
   \hline
    $ (d,k) $           &  $ (0,2) $  &  $ (1,3) $  &  $ (1,7) $  &  $ (2,7) $  &  $ (2,10) $  \\
	 \hline
	  $ \rho $            &  $ 0.544 $  &  $ 0.682 $  &  $ 0.624 $  &  $ 0.699 $  &  $ 0.687 $  \\
	 \hline
	  $ -\log\rho $       &  $ 0.879 $  &  $ 0.551 $  &  $ 0.679 $  &  $ 0.517 $  &  $ 0.542 $  \\
	 \hline
	  $ w^* $             &  $ 0.618 $  &  $ 0.363 $  &  $ 0.295 $  &  $ 0.221 $  &  $ 0.205 $  \\
	 \hline
		$ \lambda_0^* $     &  $ 0.336 $  &      -      &      -      &      -      &      -      \\
	 \hline
		$ \lambda_1^* $     &  $ 0.183 $  &  $ 0.169 $  &  $ 0.115 $  &      -      &      -      \\
	 \hline
		$ \lambda_2^* $     &  $ 0.099 $  &  $ 0.115 $  &  $ 0.072 $  &  $ 0.075 $  &  $ 0.066 $  \\
	 \hline
		$ \lambda_3^* $     &      -      &  $ 0.078 $  &  $ 0.045 $  &  $ 0.053 $  &  $ 0.046 $  \\
	 \hline
		$ \lambda_4^* $     &      -      &      -      &  $ 0.028 $  &  $ 0.037 $  &  $ 0.031 $  \\
	 \hline
		$ \lambda_5^* $     &      -      &      -      &  $ 0.017 $  &  $ 0.026 $  &  $ 0.022 $  \\
	 \hline
		$ \lambda_6^* $     &      -      &      -      &  $ 0.011 $  &  $ 0.018 $  &  $ 0.015 $  \\
	 \hline
	  $ \lambda_7^* $     &      -      &      -      &  $ 0.007 $  &  $ 0.013 $  &  $ 0.010 $  \\
	 \hline
	  $ \lambda_8^* $     &      -      &      -      &      -      &      -      &  $ 0.007 $  \\
	 \hline
	  $ \lambda_9^* $     &      -      &      -      &      -      &      -      &  $ 0.005 $  \\
	 \hline
	  $ \lambda_{10}^* $  &      -      &      -      &      -      &      -      &  $ 0.003 $  \\
	 \hline
 \end{tabular}
\label{tab:typical}
\end{table}
}

\pagebreak
\begin{remark}
\label{rem:typical}
\textnormal{
  We emphasize that the typical values $ w^* $ and $ \lambda_j^* $ depend only
on the parameters $ d, k $ which specify the allowed lengths of runs of zeros
between consecutive ones, and not on the boundary conditions adopted in the
definition of $ (d,k) $-sequences;
see the discussion after \eqref{eq:dk}--\eqref{eq:dkW}.
For example, it is irrelevant whether or not one requires the last bit to be
$ 1 $, or whether one imposes additional requirements on the lengths of the
leading and trailing runs of zeros (the so-called $ d k l r $ constraints,
see \cite[Sec. 5.4]{immink1}).
This is because the exponential growth-rate of $ (d, k) $-sequences and
constant-weight $ (d, k) $-sequences is not affected by the boundary conditions.
\myqed
}
\end{remark}

\section{Codes Correcting Asymmetric Shifts}
\label{sec:main_da}

We now turn to the analysis of the bit-shift channel with $ (d, k) $ input
constraints.
The scenario we consider in this section is the one in which right-shifts and
left-shifts of $ 1 $'s are treated independently and separate requirements on
their correctability are imposed.
In particular, we derive bounds on the cardinality of optimal codes for this
setting.
We do not attempt to optimize the bounds for every block-length $ n $;
rather, the focus is put on their asymptotic behavior as $ n \to \infty $.%

\subsection{Geometric Characterization}
\label{sec:geometry_da}

Suppose that $ \myxx \in \mySS_{d,k}(n,W) $ is the transmitted vector and
$ \bs{z} $ the corresponding received vector (see Section \ref{sec:representation}).
If the $ i $'th $ 1 $ in $ \myx $ has been shifted by $ k_i \in \mathbb{Z} $
positions in the channel, we will have $ z_i = \bar{x}_i + k_i $.
Thus, positive $ k_i $ means a right-shift and negative $ k_i $ a left-shift
by $ |k_i| $ positions.
Therefore, one can think of the bit-shift channel as an additive noise channel
with input alphabet $ \mathbb{N} \defeq \{1, 2, \ldots\} $.

In what follows, we denote by $ \bs{f}^+ \defeq \max\{ \bs{f}, \bs{0} \} $ and
$ \bs{f}^- \defeq \max\{ - \bs{f}, \bs{0} \} $ the positive and the negative
part of a vector $ \bs{f} $, so that $ \bs{f} = \bs{f}^+ - \bs{f}^- $
(here the maximum is taken coordinate-wise).
The coordinates of $ \bs{f}^+ $ and $ \bs{f}^- $ are denoted $ f_i^+ $ and $ f_i^- $,
and are all non-negative by definition.

We say that a code $ \CC \subseteq \mySS_{d,k}(n) $ corrects $ \tright $
right-shifts and $ \tleft $ left-shifts if no two different codewords
$ \myxx, \myyy \in \CC $ can produce the same output after being impaired
with arbitrary patterns of $ \tright $ or fewer right-shifts and $ \tleft $
or fewer left-shifts.
In symbols, for every $ \myxx, \myyy \in \CC $, $ \myxx \neq \myyy $,
$ {\weight(\myx) = \weight(\myy) = W} $, and all noise vectors
$ \bs{f}, \bs{g} \in \mathbb{Z}^W $ with
$ { \sum_{i}  f_i^+  \leq \tright } $,
$ { \sum_{i}  f_i^-  \leq \tleft  } $,
$ { \sum_{i}  g_i^+  \leq \tright } $,
$ { \sum_{i}  g_i^-  \leq \tleft  } $, we have
$ \myxx + \bs{f} \neq \myyy + \bs{g} $.
Such a code $ \CC $ is said to be optimal if there is no other code
$ \CC' \subseteq \mySS_{d,k}(n) $ correcting $ \tright $ right-shifts
and $ \tleft $ left-shifts and satisfying $ {|\CC'| > |\CC|} $.

Consider the following metric on $ \mySS_{d,k}(n,W)	 $:
\begin{equation}
  \da(\myxx, \myyy)  \defeq
       \max\!\left\{\sum_{i = 1}^W  (\bar{x}_i - \bar{y}_i)^+ ,
                    \sum_{i = 1}^W  (\bar{x}_i - \bar{y}_i)^-
						\right\} .
\end{equation}
This distance is of importance in the theory of codes for asymmetric channels
\cite{klove} (hence the subscript `a').
For vectors of different dimensions (corresponding to strings of different weights),
$ \myxx \in \mySS_{d,k}(n,W_1) $, $ \myyy \in \mySS_{d,k}(n,W_2) $, $ W_1 \neq W_2 $,
we define $ \da(\myxx, \myyy) = \infty $.
The minimum distance of a code $ \CC \subseteq \mySS_{d,k}(n) $ with respect to the
metric $ \da $ is denoted $ \da(\CC) $.

The following proposition gives a metric characterization of shift-correcting codes
in the asymmetric setting.

\begin{proposition}
\label{thm:da}
  A code $ \CC \subseteq \mySS_{d,k}(n) $ can correct $ \tright $ right-shifts
and $ \tleft $ left-shifts if and only if $ \da(\CC) > \tright + \tleft $.
\end{proposition}
\begin{IEEEproof}
Suppose that $ \CC $ cannot correct $ \tright $ right-shifts and $ \tleft $
left-shifts, i.e., that there exist two distinct codewords $ \myxx, \myyy $
and two noise vectors
$ \bs{f}, \bs{g} $ with
$ { \sum_{i}  f_i^+  \leq \tright } $,
$ { \sum_{i}  f_i^-  \leq \tleft  } $,
$ { \sum_{i}  g_i^+  \leq \tright } $,
$ { \sum_{i}  g_i^-  \leq \tleft  } $, such that
$ \myxx + \bs{f} = \myyy + \bs{g} $, or equivalently,
$ \myxx + \bs{f}^+ + \bs{g}^- = \myyy + \bs{g}^+ + \bs{f}^- $.
This implies that
$ \da(\myxx, \myyy) \leq \max\!\big\{\sum_{i=1}^W (f_i^+ + g_i^-), \sum_{i=1}^W (g_i^+ + f_i^-)\big\} \leq \tright + \tleft $,
and so $ \da(\CC) \leq \tright + \tleft $.

The other direction is similar.
Suppose that $ \da(\myxx, \myyy) \leq {\tright + \tleft} $ for two distinct
codewords $ \myxx, \myyy \in \CC $, and define
$ \bs{f} = (\myyy - \myxx)^+ = \max\{ \myyy - \myxx, \bs{0} \} $ and
$ \bs{g} = (\myxx - \myyy)^+ = \max\{\myxx - \myyy, \bs{0} \} $.
Then $ \myxx + \bs{f} = \myyy + \bs{g} $ and $ f_i, g_i \geq 0 $,
$ \sum_{i=1}^W f_i \leq \tright + \tleft $, $ \sum_{i=1}^W g_i \leq \tright + \tleft $
(the last two inequalities together are equivalent to our assumption that
$ \da(\myxx, \myyy) \leq \tright + \tleft $).
We can then find non-negative vectors $ \bs{f}', \bs{f}'', \bs{g}', \bs{g}'' $
satisfying $ \bs{f} = \bs{f}' + \bs{f}'' $, $ \bs{g} = \bs{g}' + \bs{g}'' $,
$ { \sum_{i} f'_i \leq \tright } $, $ { \sum_{i} f''_i \leq \tleft } $,
$ { \sum_{i} g'_i \leq \tright } $, $ { \sum_{i} g''_i \leq \tleft } $,
and write $ \myxx + \bs{f}' - \bs{g}'' = \myyy + \bs{g}' - \bs{f}'' $.
This means that $ \CC $ cannot correct $ \tright $ right-shifts and $ \tleft $
left-shifts.
\end{IEEEproof}
\vspace{2mm}

Therefore, the error-correcting capability of a code $ \CC $ depends on the
parameters $ \tright $ and $ \tleft $ only through their sum.
In other words, if one wishes to design a code capable of correcting $ \tright $
right-shifts and $ \tleft $ left-shifts, it is enough to specify only the sum
of these parameters, $ \tright + \tleft $.
In particular, $ \CC $ can correct $ \tright $ right-shifts and $ \tleft $
left-shifts if and only if it can correct $ \tright + \tleft $ right-shifts
(and $ 0 $ left-shifts).

Note the metric space $ \left(\mySS_{d,k}(n,W), \da\right) $ is not uniform in
the sense that balls in this space have varying sizes, i.e., the size of a ball
of radius $ r $ depends on its center.
For that reason, when studying properties of codes in $ \left(\mySS_{d,k}(n,W), \da\right) $
it is sometimes more convenient to consider the unrestricted metric space
$ \left(\mathbb{Z}^{W-1}, \da\right) $ (see \eqref{eq:dimW-1}) where this effect
does not occur.
For example, we have the following expression for the cardinality of a ball of radius
$ r $ in $ \left(\mathbb{Z}^{m}, \da\right) $ \cite[Lem. 1]{kovacevic+tan_it}:
\begin{equation}
\label{eq:daball}
  B_{\textnormal a}(m,r) =
     \sum_{i}  \binom{m}{i} \binom{r}{i} \binom{r + m - i}{m - i} .
\end{equation}
The cardinality of an arbitrary ball of radius $ r $ in $ \left(\mySS_{d,k}(n,W), \da\right) $
is upper bounded by $ B_{\textnormal a}(W-1,r) $.

The geometric notions discussed thus far---the metric space $ \left(\mySS_{d,k}(n,W), \da\right) $
and codes in this space---are illustrated in Figure~\ref{fig:code_da}
for specific values of the parameters $ d, k, n, W $.

\begin{figure
\centering
  \includegraphics[width=\columnwidth]{da_dk5}
\caption{The space $ \mySS_{1,7}(11,3) \subset \mathbb{Z}^2\!\times\!\{11\} $
representing the set of all binary strings of length $ n = 11 $ and weight
$ W = 3 $ satisfying the $ (1,7) $-constraint, and a code of minimum distance
$ \delta = 3 $ with respect to the metric $ \da $.
Codewords are depicted as black dots.
Gray regions illustrate balls of radius
$ \lfloor\frac{\delta-1}{2}\rfloor = 1 $ around the codewords.}
\label{fig:code_da}
\end{figure}%

\subsection{Construction and Bounds}

Denote by $ \Ma_{d,k}(n; t) $ (resp. $ \Ma_{d,k}(n, W; t) $) the cardinality
of an optimal code in $ \myS_{d,k}(n) $ (resp. $ \myS_{d,k}(n,W) $) of minimum
distance larger than $ t $ with respect to the metric $ \da $.
Since the channel does not affect the weight of the transmitted string, we know
that $ \Ma_{d,k}(n; t) = \sum_{W} \Ma_{d,k}(n, W; t) $.
The parameter $ t $ in this notation can also be understood as the sum of the
numbers of correctable right-shifts and left-shifts
(see Proposition \ref{thm:da}).

The lower bound on $ \Ma_{d,k}(n; t) $ given in Theorem \ref{thm:bounds_a_fixed}
below is obtained by constructing a family of codes in
$ \left(\mySS_{d,k}(n,W), \da\right) $, which in turn is done
by using ``good'' codes in $ \left(\mathbb{Z}^{W-1}, \da\right) $,
translating them to $ \left(\mathbb{Z}^{W-1} \!\times\! \{n\}, \da\right) $,
and then restricting to $ \mySS_{d,k}(n,W) $.
For that reason, a lower bound for codes in $ \left(\mathbb{Z}^{W-1}, \da\right) $
is given first (Lemma \ref{thm:density_a}).
This bound was essentially obtained in \cite{kovacevic+tan_it} but was not
stated there formally so we give it here for completeness.
A few definitions are needed to state it precisely.

We say that $ {\mathcal L} \subseteq \mathbb{Z}^m $ is a sublattice of
$ \mathbb{Z}^m $ if $ ({\mathcal L}, +) $ is a subgroup of $ \big(\mathbb{Z}^m, +\big) $.
The density of $ {\mathcal L} $ in $ \mathbb{Z}^m $ is defined as
$ \mu({\mathcal L}) \defeq \big|\mathbb{Z}^m / {\mathcal L}\big|^{-1} $,
where $ \mathbb{Z}^m / {\mathcal L} $ is the quotient group of $ \mathcal L $,
and represents the average number of lattice points (from $ \mathcal L $)
per one point of the ambient space ($ \mathbb{Z}^m $).
The quantity of interest to us in the present context is the maximum density
a lattice $ {\mathcal L} \subseteq \mathbb{Z}^m $ can have when its minimum
distance is required to satisfy $ \da({\mathcal L}) > t $, namely
\begin{equation}
\label{eq:mu_a}
  \mu_{\textnormal a}(m, t)  \defeq
    \max\!\Big\{ \mu({\mathcal L}) \, : \, {\mathcal L} \subseteq \mathbb{Z}^m \, \text{a lattice}, \,
		                                \da({\mathcal L}) > t \Big\} .
\end{equation}

\begin{lemma}
\label{thm:density_a}
For every $ t \geq 1 $, as $ m \to \infty $ we have
\begin{equation}
\label{eq:density_a}
  \mu_{\textnormal a}(m, t)  \gtrsim  \frac{1}{m^{t}} .
\end{equation}
For $ t \leq 2 $ this lower bound is tight, i.e.,
\begin{equation}
\label{eq:density_a1}
	\mu_{\textnormal a}(m,1)  \sim  \frac{1}{m} , \quad
	\mu_{\textnormal a}(m,2)  \sim  \frac{1}{m^2} .
\end{equation}
\end{lemma}
\begin{IEEEproof}
It was shown in \cite[Thm 7]{kovacevic+tan_it} that every sublattice
$ {\mathcal L} \subseteq \mathbb{Z}^m $ with $ {\da({\mathcal L}) > t} $
corresponds to a Sidon set%
\footnote{A Sidon set of order $ t $ in an Abelian group $ (G, +) $ is any subset
$ \{b_0, b_1, \ldots, b_m\} \subseteq G $ with the property that all its $ t $-sums
($ b_{i_1} + \cdots + b_{i_t} $) are distinct, up to the order of the summands;
see \cite{obryant, kovacevic+tan_sidma}.}
of order $ t $ and cardinality $ m + 1 $ in an Abelian group, and vice versa.
Consequently, the largest possible density of such a sublattice can be expressed
as $ \mu_{\textnormal a}(m,t) = \frac{1}{\phi(m,t)} $, where $ \phi(m,t) $ denotes
the size of the smallest Abelian group containing a Sidon set of order $ t $ and
cardinality $ m + 1 $.
The relation \eqref{eq:density_a} then follows from the Bose--Chowla construction
of Sidon sets \cite{bose+chowla} which implies that $ \phi(m,t) \leq m^{t} + m^{t-1} + \cdots + 1 $
when $ m $ is a prime power.
For $ t = 2 $ and $ m $ a prime power this construction (obtained earlier by Singer
\cite{singer}) is known to be optimal, i.e., $ \phi(m,2) = m^2 + m + 1 $, which,
together with the obvious fact that $ \phi(m,1) = m + 1 $ for every $ m $, implies
\eqref{eq:density_a1}.
\end{IEEEproof}

\begin{theorem}
\label{thm:bounds_a_fixed}
\begin{subequations}
\label{eq:bounds_a}
  For every $ t \geq 1 $ and $ d, k $ with $ 0 \leq d < k \leq \infty $,
as $ n \to \infty $ we have
\begin{align}
\label{eq:bounds_a_lower}
    \Ma_{d,k}(n; t)  &\gtrsim
		  \frac{S_{d,k}(n)}{n^{t}} \left( \sum_{i=d+1}^{k+1} i \rho^{i} \right)^{t}  ,  \\
\label{eq:bounds_a_upper}
	  \Ma_{d,k}(n; t)  &\lesssim
      \frac{S_{d,k}(n)}{n^{t}} \left( \sum_{i=d+1}^{k+1} i \rho^{i} \right)^{t}
        \!\frac{ \ceil{t/2}! \floor{t/2}! }{ \big( (1 - \rho^{d+1}) (1 - \rho^{k+1}) \big)^{t} } ,
\end{align}
where $ \rho $ is the unique positive solution to $ \sum_{i=d+1}^{k+1}  x^{i} = 1 $.
\end{subequations}
\end{theorem}
\begin{IEEEproof}
  We first derive the lower bound \eqref{eq:bounds_a_lower}.
Consider a class of codes in $ \mySS_{d,k}(n,W) $ obtained in the following way:
Take a lattice $ {\mathcal  L} \subseteq \mathbb{Z}^{W-1} $ of minimum distance
$ \da({\mathcal L}) = t + 1 $, and let
$ {\C}_{\bs{u}} \defeq \big((\bs{u} + {\mathcal L})\!\times\!\{n\}\big) \cap \mySS_{d,k}(n,W) $
for an arbitrary $ \bs{u} \in \mathbb{Z}^{W-1} $
(here $ \bs{u} + {\mathcal L} = \{\bs{u} + \bs{x} : \bs{x} \in {\mathcal L}\} $).
Clearly, the code $ {\C}_{\bs{u}} $ has minimum distance
$ \da({\C}_{\bs{u}}) > t $.
To give a lower bound on its cardinality notice that there are
$ \big|\mathbb{Z}^{W-1} / {\mathcal L}\big| = \mu({\mathcal L})^{-1} $
different translates $ \bs{u} + {\mathcal L} $ that are disjoint and whose
union is all of $ \mathbb{Z}^{W-1} $, so there exists at least one $ \bs{u} $
for which
$ \big|{\C}_{\bs{u}}\big| =
  \big| \big((\bs{u} + {\mathcal L})\!\times\!\{n\}\big) \cap \mySS_{d,k}(n,W) \big| \geq
  \mu({\mathcal L}) \cdot S_{d,k}(n,W) $.
This establishes the existence of a code in $ \mySS_{d,k}(n,W) $ of minimum distance
$ > t $ and cardinality $ \geq \mu_{\textnormal a}(W-1,t) \cdot S_{d,k}(n,W) $.
From Lemma \ref{thm:density_a} we then conclude that
$ \Ma_{d,k}(n, wn; t) \gtrsim \frac{S_{d,k}(n,wn)}{(w n)^{t}} $.
Finally, to get the desired lower bound on $ \Ma_{d,k}(n; t) $ write:
\begin{align}
  \Ma_{d,k}(n; t)
    \label{eq:aa}
    &=     \sum_{W}  \Ma_{d,k}(n, W; t)   \\
    &>     \sum_{W = w^*n - f(n)}^{w^*n + f(n)}  \Ma_{d,k}(n, W; t)   \\
		\label{eq:1}
    &\geq  \sum_{W = w^*n - f(n)}^{w^*n + f(n)}  \mu_{\textnormal a}(W,t) \cdot S_{d,k}(n,W)   \\
    \label{eq:2}
		&\gtrsim  \frac{ 1 }{ (w^*n + f(n))^{t} } \sum\limits_{W = w^*n - f(n)}^{w^*n + f(n)}  S_{d,k}(n,W)   \\
    \label{eq:3}
		&\sim  \frac{ S_{d,k}(n) }{ (w^*n)^{t} }  ,
\end{align}
where $ w^* $ is the optimizing weight given in Lemma \ref{thm:expW} and
$ f(n) $ is the sublinear function from Lemma \ref{thm:typicalw}.
Here \eqref{eq:1} follows from our code construction, \eqref{eq:2} follows from
Lemma \ref{thm:density_a}, and \eqref{eq:3} follows from Lemma \ref{thm:typicalw}
and the fact that $ f(n) = o(n) $.

We now turn to the derivation of the upper bound \eqref{eq:bounds_a_upper}.
Our approach is essentially a packing argument; however, due to the structure
of the code space and the fact that balls in it do not have uniform sizes, some
care is needed in making the argument work.
Let $ \C \subseteq \myS_{d,k}(n) $ be an optimal code correcting $ \floor{t/2} $
right-shifts and $ \ceil{t/2} $ left-shifts, $ |\C| = \Ma_{d,k}(n; t) $
(see Proposition \ref{thm:da}).
Consider a codeword $ \myx \in \C $ of weight $ W $, and let $ \Lambda_{j} $
(resp. $ {_j}\Lambda $) denote the number of $ 1 $'s in $ \myx $ that are
followed (resp. preceded) by exactly $ j $ zeros, and $ \Lambda_{\neq j} $
(resp. $ {_{\neq j}}\Lambda $) the number of $ 1 $'s in $ \myx $ that are
followed (resp. preceded) by a run of zeros whose length is \emph{not} $ j $.
Also, let $ {_i}\Lambda_{j} $ denote the number of $ 1 $'s in $ \myx $ that are
preceded by exactly $ i $ zeros \emph{and} followed by exactly $ j $ zeros;
$ {_i}\Lambda_{\neq j} $ the number of $ 1 $'s in $ \myx $ that are preceded by
exactly $ i $ zeros \emph{and} followed by a run of zeros whose length is \emph{not}
$ j $; and similarly for $ {_{\neq i}}\Lambda_{j} $ and $ {_{\neq i}}\Lambda_{\neq j} $.
We next show that the number of strings in $ \myS_{d,k}(n) $ that can be obtained
after $ \myx $ is impaired by $ \floor{t/2} $ right-shifts and $ \ceil{t/2} $
left-shifts is at least
\begin{equation}
\label{eq:right-shifts}
  \binom{ {_{\neq k}}\Lambda_{\neq d} - 1   }{ \floor{t/2} }
  \binom{ {_{\neq d}}\Lambda_{\neq k} - 2 t }{ \ceil{t/2}  } .
\end{equation}
To see this, first count the number of strings that can be obtained by shifting
$ \floor{t/2} $ $ 1 $'s one position to the right.
In other words, pick $ \floor{t/2} $ out of $ W $ $ 1 $'s, and shift each of them
one position to the right.
Notice that not all such choices will result in a string that belongs to our code
space $ \myS_{d,k}(n) $.
Namely, right-shifting a $ 1 $ that
\begin{inparaenum}
\item[(a)]
is preceded by exactly $ k $ zeros, or
\item[(b)]
is followed by exactly $ d $ zeros, or
\item[(c)]
is the last symbol in the string,
\end{inparaenum}
would result in either a string that violates the $ (d,k) $-constraints, or is
of length $ n + 1 $.
Excluding the $ 1 $'s satisfying (a)--(c) leaves us with at least
$ {_{\neq k}}\Lambda_{\neq d} - 1 $ $ 1 $'s to choose from, which gives the left-hand
term in \eqref{eq:right-shifts}.
The right-hand term is obtained in an analogous way by counting the number of strings
that can be obtained after picking $ \ceil{t/2} $ out of $ {_{\neq d}}\Lambda_{\neq k} - 1 $
$ 1 $'s and shifting each of them one position to the left.
The difference here is that, after choosing $ \floor{t/2} $ $ 1 $'s for the right-shifts
in the first step, we exclude additional $ 3 \floor{t/2} $ $ 1 $'s  in the second step.
Namely, if the $ i $'th $ 1 $ has been chosen for the right-shift in the first step,
then the $ (i-1) $'th, the $ i $'th, and the $ (i+1) $'th $ 1 $ are excluded in the
second step:
the $ i $'th because right-shifting and then left-shifting the same $ 1 $ would
potentially result in the same string we started with, and the $ (i-1) $'th
(resp. $ (i+1) $'th) because right-shifting the $ i $'th $ 1 $ and then left-shifting
the $ (i-1) $'th (resp. $ (i+1) $'th) could result in a run of zeros of length
$ k + 1 $ (resp. $ d - 1 $) in between these $ 1 $'s.
We are thus left with at least
$ {_{\neq d}}\Lambda_{\neq k} - 3 \ceil{t/2} - 1 \geq {_{\neq d}}\Lambda_{\neq k} - 2 t $
$ 1 $'s to choose from, which yields the right-hand term in \eqref{eq:right-shifts}.
This proves our claim that the expression in \eqref{eq:right-shifts} is a lower bound
on the number of strings in $ \myS_{d,k}(n) $ that $ \myx $ can produce after being
impaired by $ \floor{t/2} $ right-shifts and $ \ceil{t/2} $ left-shifts.

We next give the asymptotic form of \eqref{eq:right-shifts}, for fixed $ t $
and $ n \to \infty $, that will be needed to conclude the proof.
We know from Lemma \ref{thm:typicaldk} that, for the ``typical'' strings in
$ \myS_{d,k}(n) $, $ {W \sim w^* n} $ and
$ {_j}\Lambda \sim \Lambda_j \sim \lambda_j^* n = \rho^{j+1} w^* n $, $ d \leq j \leq k $.
This implies that a given block $ 0^j 1 $ is preceded by a block $ 0^i 1 $ with
probability
$ \approx \frac{\lambda_i^*}{w^*} = \rho^{i+1} $, or in other words, of the
$ \Lambda_{j} $ blocks $ 0^j 1 $, a fraction of $ \approx \rho^{i+1} $ is preceded
by a block $ 0^i 1 $.
It follows that, for the typical strings in $ \myS_{d,k}(n) $,
$ {_{\neq d}}\Lambda_{\neq k}  \sim  w^* (1 - \rho^{d+1}) (1 - \rho^{k+1}) n $,
and therefore the expression \eqref{eq:right-shifts} has the following asymptotic
form:
\begin{equation}
\label{eq:shiftsasymp}
  \sim \frac{ \big(w^* (1 - \rho^{d+1}) (1 - \rho^{k+1})\big)^{t} n^{t} }{ \ceil{t/2}! \floor{t/2}! }  ,
\end{equation}
where we have used the fact that $ \binom{n}{m} \sim \frac{n^m}{m!} $ for
fixed $ m $ and $ n \to \infty $.

Finally, due to our assumption that $ \C $ corrects $ \floor{t/2} $ right-shifts
and $ \ceil{t/2} $ left-shifts, the sets of outputs that can be obtained in the
above-described way from any two different codewords $ \myx, \myy \in \C $ have
to be disjoint.
This implies that
\begin{align}
\label{eq:upper2}
  \Ma_{d,k}(n; t) \cdot
   \frac{ \big(w^* (1 - \rho^{d+1}) (1 - \rho^{k+1})\big)^{t} n^{t} }{ \ceil{t/2}! \floor{t/2}! }
    \lesssim  S_{d,k}(n)
\end{align}
and proves the upper bound in \eqref{eq:bounds_a_upper}.
We have used in \eqref{eq:upper2} the fact that in the asymptotic analysis we
can safely ignore the non-typical inputs (see Lemma \ref{thm:typicaldk}), as
we did in the derivation of the lower bound as well.
\end{IEEEproof}

\begin{corollary}
  For every $ t \geq 1 $ and $ d, k $ with $ 0 \leq d < k \leq \infty $,
as $ n \to \infty $ we have
\begin{equation}
  \log \Ma_{d,k}(n; t)  =
      - n \log \rho  -  t \log n  +  {\mathcal O}(1) ,
\end{equation}
where $ \rho $ is the unique positive solution to $ \sum_{i=d+1}^{k+1}  x^{i} = 1 $.
\end{corollary}
\begin{IEEEproof}
  Follows from Theorem \ref{thm:bounds_a_fixed} and the fact that
$ S_{d,k}(n) \sim c \rho^{-n} $ for a constant $ c $.
\end{IEEEproof}
\vspace{2mm}

For example, in the unconstrained case ($ d = 0, k = \infty $) we have
$ S_{0,\infty}(n) = 2^{n-1} $, $ \rho = 1/2 $, and the bounds \eqref{eq:bounds_a}
reduce to:
\begin{equation}
\label{eq:unconstrained_a}
  \frac{2^{n-1}}{n^{t}} 2^{t}
	  \lesssim
	    \Ma_{0,\infty}(n; t)
		\lesssim
  \frac{2^{n-1}}{n^{t}} 4^{t} \ceil{t/2}! \floor{t/2}! .
\end{equation}

To conclude this section, we note that the bounds \eqref{eq:bounds_a} would
continue to hold if we had adopted different boundary conditions in the
definition of $ (d, k) $-sequences \eqref{eq:dk}, because these conditions do
not affect the typical values $ w^* $ and $ \lambda_j^* $ (see Remark \ref{rem:typical}).
Of course, in that case $ S_{d,k}(n) $ in \eqref{eq:bounds_a} would represent
the cardinality of the corresponding code space, not the cardinality of the
code space considered in this paper (see \eqref{eq:Sdkrec}).
For example, if we do not require the last bit to be $ 1 $, the bounds for the
unconstrained case would be the same as those in \eqref{eq:unconstrained_a},
with $ 2^{n-1} $ replaced by $ 2^n $.

More generally, our construction and method of deriving the bounds can be
used for the bit-shift channel with other types of input constraints---a
code would be constructed by intersecting the code space with a translated
lattice having the desired minimum distance, and the upper bound would be
derived by an analogous packing argument.
Note that, to state the resulting bounds explicitly, the typical values $ w^* $
and $ \lambda_j^* $ would first have to be determined for the constraint in
question.
Still more generally, the same approach can be used in some other weight-preserving
channels as well, such as the channel with insertions and deletions of blocks
of zeros \cite{levenshtein, kovacevic+tan_clet}.

\section{Codes Correcting Symmetric Shifts}
\label{sec:main_d1}

In this section we discuss a slightly different scenario---the one which is usually
considered in the literature on bit-shift channels---where left-shifts and right-shifts
are treated in a symmetric way.
Our object of study are codes that enable the receiver to reconstruct the transmitted
string whenever the total shift of its $ 1 $'s does not exceed a specified threshold,
regardless of the direction of each individual shift.

\subsection{Geometric Characterization}
\label{sec:geometry_d1}

Suppose that $ \myxx \in \mySS_{d,k}(n) $ is the transmitted codeword, and $ \bs{z} $
the corresponding received vector.
If the $ 1 $'s in $ \myxx $ have been shifted by $ t $ positions in total, then
$ \sum_{i=1}^W |z_i - \bar{x}_i| = t $.

We say that a code $ \CC \subseteq \mySS_{d,k}(n) $ can correct $ t $ \emph{shifts}
if no two different codewords $ \myxx, \myyy \in \CC $ can produce the same output
after being impaired with arbitrary patterns of $ t $ or fewer shifts.
In symbols, for every $ \myxx, \myyy \in \CC $, $ \myxx \neq \myyy $,
$ \weight(\myx) = \weight(\myy) = W $, and all
noise vectors $ \bs{f}, \bs{g} \in \mathbb{Z}^W $ with
$ \sum_{i=1}^W |f_i| \leq t $, $ \sum_{i=1}^W |g_i| \leq t $, we have
$ \myxx + \bs{f} \neq \myyy + \bs{g} $.
Such a code $ \CC $ is said to be optimal if there is no other code
$ \CC' \subseteq \mySS_{d,k}(n) $ correcting $ t $ shifts and such that
$ |\CC'| > |\CC| $.

Let $ \ds $ denote the Manhattan distance on $ \mySS_{d,k}(n,W) $:
\begin{equation}
  \ds(\myxx, \myyy)
    \defeq  \sum_{i = 1}^W |\bar{x}_i - \bar{y}_i|
\end{equation}
For vectors of different dimensions (corresponding to strings of different weights),
$ \myxx \in \mySS_{d,k}(n,W_1) $, $ \myyy \in \mySS_{d,k}(n,W_2) $, $ W_1 \neq W_2 $,
we set $ \ds(\myxx, \myyy) = \infty $.
The minimum distance of a code $ \CC \subseteq \mySS_{d,k}(n) $ with respect to
the metric $ \ds $ is denoted $ \ds(\CC) $.
The metric space $ \left(\mySS_{d,k}(n,W), \ds\right) $ and a code in this space
are illustrated in Figure \ref{fig:code_d1} for specific values of the parameters
$ d, k, n, W $.

The following proposition gives a metric characterization of shift-correcting
codes in the symmetric setting.
It was first stated in \cite[Thm 1]{kolesnik+krachkovsky} (in a more general form)
but is also implicit in some of the earlier works, e.g., \cite{abdelghaffar+weber}.

\begin{proposition}
\label{thm:d1}
  A code $ \CC \subseteq \mySS_{d,k}(n) $ can correct $ t $ shifts if and only if
$ \ds(\CC) > 2t $.
\hfill \IEEEQED
\end{proposition}
\vspace{2mm}

\begin{figure
\centering
  \includegraphics[width=\columnwidth]{d1_dk5}
\caption{The space $ \mySS_{1,7}(11,3) \subset \mathbb{Z}^2\!\times\!\{11\} $
representing the set of all binary strings of length $ n = 11 $ and weight
$ W = 3 $ satisfying the $ (1,7) $-constraint, and a code of minimum distance
$ \delta = 3 $ with respect to the metric $ \ds $.
Codewords are depicted as black dots.
Gray regions illustrate balls of radius $ \floor{\frac{\delta-1}{2}} = 1 $
around the codewords.}
\label{fig:code_d1}
\end{figure}%

Again, the space $ \left(\mySS_{d,k}(n,W), \ds\right) $ is not uniform in the
sense that ball sizes depend on the locations of their centers.
In the unrestricted space $ \left(\mathbb{Z}^{W-1}, \ds\right) $ this effect
does not occur and we have the following expression for the cardinality of a
ball of radius $ r $ in $ \left(\mathbb{Z}^{m}, \ds\right) $ \cite{golomb+welch}:
\begin{equation}
\label{eq:d1ball}
  B_\textnormal{s}(m, r) = \sum_{i}  2^i \binom{m}{i} \binom{r}{i} .
\end{equation}
The cardinality of an arbitrary ball of radius $ r $ in $ \left(\mySS_{d,k}(n,W), \ds\right) $
is upper bounded by $ B_{\textnormal{s}}(W-1,r) $.

\subsection{Construction and Bounds}

Let $ \Ms_{d,k}(n; t) $ (resp. $ \Ms_{d,k}(n, W; t) $) denote the cardinality
of an optimal code in $ \myS_{d,k}(n) $ (resp. $ \myS_{d,k}(n,W) $) correcting
$ t $ shifts, or equivalently, having minimum distance larger than $ 2t $ with
respect to the metric $ \ds $.
Since the channel does not affect the weight of the transmitted string, we have
$ \Ms_{d,k}(n; t) = \sum_{W} \Ms_{d,k}(n, W; t) $.

In analogy with \eqref{eq:mu_a} we define the maximum density a lattice
$ {\mathcal L} \subseteq \mathbb{Z}^m $ with $ \ds({\mathcal L}) > 2t $
can have as%
\begin{equation}
  \mu_{\textnormal{s}}(m,t)  \defeq
    \max\!\Big\{ \mu({\mathcal L}) \, : \, {\mathcal L} \subseteq \mathbb{Z}^m \, \text{a lattice},\,
		                                \ds({\mathcal L}) > 2t \Big\} .
\end{equation}

\begin{lemma}
\label{thm:density_1}
For every $ t \geq 1 $, as $ m \to \infty $ we have
\begin{equation}
\label{eq:density_1}
  \mu_{\textnormal{s}}(m, t)  \gtrsim  \frac{c(t)}{m^{t}} ,
\end{equation}
where
\begin{equation}
\label{eq:ct}
  c(t) \defeq
	\begin{cases}
	\frac{1}{2t}   ,   &  t \leq 2  \\
	\frac{1}{2t+1} ,   &  t \geq 3
  \end{cases} .
\end{equation}
For $ t = 1 $ this lower bound is tight, i.e.,
\begin{equation}
\label{eq:density_11}
	\mu_{\textnormal s}(m,1)  \sim  \frac{1}{2m} .
\end{equation}
\end{lemma}
\begin{IEEEproof}
  Consider the so-called $ A_{m-1} $ lattice defined by
$ A_{m-1} \defeq \big\{ (u_1, \ldots, u_m) \in \mathbb{Z}^m : \sum_{i=1}^m u_i = 0 \big\} $,
and let $ {\mathcal L}_0 $ be the densest sublattice of $ A_{m-1} $ satisfying
$ \ds({\mathcal L}_0) > 2t $.
By \cite[Thm 4]{kovacevic+tan_it}, the metric space $ (A_{m-1}, \ds) $ is
isometric to $ (\mathbb{Z}^{m-1}, 2 \da) $, so the density of $ {\mathcal L}_0 $
in $ A_{m-1} $ can be expressed as
$ \mu({\mathcal L}_0) \defeq | A_{m-1} / {\mathcal L}_0 |^{-1}
  = \mu_{\textnormal{a}}\big(m-1, t\big) $.
Now define a lattice $ {\mathcal L} \subseteq \mathbb{Z}^m $ by
$ {\mathcal L} \defeq \bigcup_{k \in \mathbb{Z}} \big( {\mathcal L}_0 + k (2t + 1) \bs{e}_1 \big) $,
where $ \bs{e}_1 = (1, 0, \ldots, 0) $ is a unit vector in $ \mathbb{Z}^m $.
In words, $ {\mathcal L} $ comprises infinitely many translates of $ {\mathcal L}_0 $
separated by a multiple of $ 2t + 1 $.
It follows from the construction that $ \ds({\mathcal L}) \geq 2t + 1 $ and
$ \mu({\mathcal L}) \defeq | \mathbb{Z}^m / {\mathcal L} |^{-1}
  = \frac{1}{2t + 1} \mu({\mathcal L}_0)
  = \frac{1}{2t + 1} \mu_{\textnormal{a}}(m-1, t) $,
which, together with Lemma \ref{thm:density_a}, implies that
$ \mu_{\textnormal{s}}(m, t) \gtrsim \frac{1}{2t+1} m^{-t} $.

The lower bound just given can be improved for $ t = 1, 2 $  to
$ \mu_{\textnormal{s}}(m,t) \gtrsim \frac{1}{2t} m^{-t} $.
In fact, for $ t = 1 $ the optimal density is known exactly for every $ m $:
$ \mu_{\textnormal{s}}(m,1) = \frac{1}{2 m + 1} $.
This follows from the existence of perfect codes of radius $ t = 1 $ in
$ (\mathbb{Z}^{m}, \ds) $, for every $ m $ \cite{golomb+welch}.
For $ t = 2 $ (or, indeed, for any $ t $), one can construct codes in
$ (\mathbb{Z}^{m}, \ds) $ by periodically extending the codes in the torus
$ \mathbb{Z}_q^m $ correcting $ t = 2 $ errors in the Lee metric%
\footnote{To the best of our knowledge, no known construction of codes in the
Lee metric gives a lower bound on the density $ \mu_{\textnormal{s}}(m,t) $ better
than the one obtained above, except for $ t = 1, 2 $.
For example, Berlekamp's construction \cite[Ch.\ 9]{berlekamp} (see also \cite{chiang+wolf})
gives $ \mu_{\textnormal{s}}(m,t) \gtrsim 2^{-t} m^{-t} $, and the BCH-like
construction of Roth and Siegel \cite{roth+siegel} gives
$ \mu_{\textnormal{s}}(m,t) \gtrsim p_{2t+3}^{-1} m^{-t} $,
where $ p_{2t+3} $ is the smallest prime greater than or equal to $ 2t+3 $.}
(here $ \mathbb{Z}_q \defeq \mathbb{Z} / (q \mathbb{Z}) $).
Such a periodic extension of Berlekamp's codes for the Lee metric \cite[Ch.\ 9]{berlekamp}
gives $ \mu_{\textnormal{s}}(m,2) \gtrsim \frac{1}{4} m^{-2} $.
\end{IEEEproof}

\begin{theorem}
\label{thm:bounds_1_fixed}
\begin{subequations}
\label{eq:bounds_1}
  For every $ t \geq 1 $ and $ d, k $ with $ 0 \leq d < k \leq \infty $,
as $ n \to \infty $ we have
\begin{align}
\label{eq:bounds_1_lower}
   \Ms_{d,k}(n; t)  &\gtrsim
		  \frac{ S_{d,k}(n) }{ n^{t} } \left( \sum_{i=d+1}^{k+1} i \rho^{i} \right)^{t} c(t)  ,  \\
\label{eq:bounds_1_upper}
	 \Ms_{d,k}(n; t)  &\lesssim
      \frac{ S_{d,k}(n) }{ n^{t} } \left( \sum_{i=d+1}^{k+1} i \rho^{i} \right)^{t}
        \!\frac{ t! \, 2^{-t} }{ \big( (1 - \rho^{d+1}) (1 - \rho^{k+1}) \big)^{t} } ,
\end{align}
where $ c(t) $ is defined in \eqref{eq:ct} and $ \rho $ is the unique
positive solution to $ \sum_{i=d+1}^{k+1}  x^{i} = 1 $.
\end{subequations}
\end{theorem}
\begin{IEEEproof}
  The proof is analogous to the proof of Theorem \ref{thm:bounds_a_fixed} for
the asymmetric case.
The only difference in proving the lower bound \eqref{eq:bounds_1_lower} is
that we need to use the metric $ \ds $ instead of $ \da $ (see Proposition
\ref{thm:d1}).
Following the same steps as in \eqref{eq:aa}--\eqref{eq:3} we get
$ \Ms_{d,k}(n; t)  \gtrsim  \mu_{\textnormal{s}}(w^*n, t) \cdot S_{d,k}(n) $,
and then the result follows by applying Lemma \ref{thm:density_1}.

Now for the upper bound \eqref{eq:bounds_1_upper}.
Let $ \C \subseteq \myS_{d,k}(n) $ be an optimal code correcting $ t $
shifts, $ |\C| = \Ms_{d,k}(n; t) $, and consider a codeword $ \myx \in \C $.
Every pattern of $ t $ shifts that can impair $ \myx $ in the channel
consists of $ r $ right-shifts and $ t - r $ left-shifts, for some
$ r \in \{0, 1, \ldots, t\} $.
By a reasoning identical to that used in the proof of Theorem \ref{thm:bounds_a_fixed}
we then conclude that the number of strings in $ \myS_{d,k}(n) $ that can be
produced after $ \myx $ is impaired by $ t $ shifts is at least
\begin{equation}
\label{eq:shifts}
  \sum_{r=0}^t
	  \binom{ {_{\neq k}}\Lambda_{\neq d} - 1  }{ r }
    \binom{ {_{\neq d}}\Lambda_{\neq k} - 3 r - 1 }{ t - r }
\end{equation}
(see equation \eqref{eq:right-shifts} and the paragraph following it).
Recalling that
$ {_{\neq d}}\Lambda_{\neq k}  \sim  {_{\neq k}}\Lambda_{\neq d}
  \sim  w^* (1 - \rho^{d+1}) (1 - \rho^{k+1}) n $ as
$ n \to \infty $, we find the asymptotics of the expression \eqref{eq:shifts}
in the form:
\begin{align}
\label{eq:shift2sasymp}
\nonumber
  &\sim \sum_{r=0}^t
	  \frac{ \big( {_{\neq k}}\Lambda_{\neq d} \big)^r }{ r! }
    \frac{ \big( {_{\neq d}}\Lambda_{\neq k} \big)^{t-r} }{ (t - r)! }
    \;\; \sim
    \frac{ 2^t }{ t! }  \big( {_{\neq k}}\Lambda_{\neq d} \big)^t   \\
		&\sim
		\frac{ 2^t }{ t! }  \big( w^*  (1 - \rho^{d+1})  (1 - \rho^{k+1}) \big)^t  n^t  .
\end{align}
Since $ \C $ corrects $ t $ shifts by assumption, we must have
\begin{align}
  \Ms_{d,k}(n; t)  \cdot
     \frac{ 2^t }{ t! }  \big( w^*  (1 - \rho^{d+1})  (1 - \rho^{k+1}) \big)^t  n^t
   \lesssim  S_{d,k}(n)  ,
\end{align}
which is equivalent to \eqref{eq:bounds_1_upper}.
\end{IEEEproof}
\vspace{2mm}

\begin{corollary}
For every $ t \geq 1 $ and $ d, k $ with $ 0 \leq d < k \leq \infty $,
as $ n \to \infty $ we have
\begin{equation}
  \log \Ms_{d,k}(n; t)  =  - n \log\rho - t \log n  +  {\mathcal O}(1) ,
\end{equation}
where $ \rho $ is the unique positive solution to $ \sum_{i=d+1}^{k+1}  x^{i} = 1 $.
\hfill \IEEEQED
\end{corollary}
\vspace{2mm}

In the unconstrained case ($ d = 0, k = \infty $) we have
$ S_{0,\infty}(n) = 2^{n-1} $, $ \rho = 1/2 $, and the bounds \eqref{eq:bounds_1}
reduce to:
\begin{equation}
\label{eq:unconstrained1}
  \frac{2^{n-1}}{n^{t}} 2^t c(t)
    \lesssim
	   \Ms_{0,\infty}(n; t)
	  \lesssim
  \frac{2^{n-1}}{n^{t}} 2^t t! .
\end{equation}

Similarly as in the asymmetric case, the bounds \eqref{eq:bounds_1} would
continue to hold if we had adopted different boundary conditions in the definition
of $ (d, k) $-sequences \eqref{eq:dk}, because these conditions do not affect
the typical values $ w^* $ and $ \lambda_j^* $ (see Remark \ref{rem:typical}).
For example, if one does not fix the value of the last bit, the bounds for the
unconstrained case would be the same as those in \eqref{eq:unconstrained1},
with $ 2^{n-1} $ replaced by $ 2^n $.

\section{Concluding Remarks}
\label{sec:conclusion}

We conclude the paper with a few remarks on error models related to those we have
studied here.

In some applications it is reasonable to assume that the shifts are limited in the
sense that each $ 1 $ in an input string $ \myx $ can be shifted by at most $ s $
positions \cite{abdelghaffar+weber, krachkovsky, shamai+zehavi}.
More precisely, if $ \myxx $ is the transmitted vector and $ \bs{z} $ the received
vector, the assumption here is that $ | z_i - \bar{x}_i | \leq s $, $ {1 \leq i \leq n} $.
For such models, the lower bound on the cardinality of optimal shift-correcting codes
can possibly be improved by using the known constructions of codes for limited-magnitude
errors; see, e.g., \cite{cassuto}.
For example, in the asymmetric case with $ \tright + \tleft = 2 $, $ s = 1 $,
the lower bound in \eqref{eq:bounds_a_lower} can be improved by a factor of $ 2 $
by using a construction of codes correcting $ 2 $ asymmetric $ 1 $-limited-magnitude
errors \cite[Sec. IV.C]{cassuto}.
Note that we have implicitly used the assumption that $ s = 1 $ in our derivation
of the upper bounds \eqref{eq:bounds_a_upper} and \eqref{eq:bounds_1_upper}.
Therefore, these upper bounds are not likely to be improved in limited-shift
models by using the approach we have used.

In this context one may also be interested in codes correcting \emph{all}
possible patterns of shifts such that each shift is bounded by $ s $.
Such (zero-error) codes have been studied in several related settings:
bit-shift channels \cite{shamai+zehavi, krachkovsky}, timing channels
\cite{kovacevic+popovski, kovacevic+stojakovic+tan}, skew-tolerant parallel
asynchronous communications \cite{engelberg+keren, kovacevic}, etc.
In many cases, the optimal codes have been found and the zero-error capacity
of the corresponding channel determined.

\section*{Acknowledgment}

The author would like to thank
Vincent Y. F. Tan (NUS), for his detailed reading and helpful comments on a preliminary
version of this work;
Mehul Motani (NUS), for several discussions on a model related to the one studied
in this paper;
Anshoo Tandon (NUS), for the many helpful discussions on constrained codes and
related notions;
and the three anonymous referees, whose detailed comments and corrections have
significantly improved the manuscript.

redpajama_set_name: RedPajamaArXiv


text:
Day 01: Southern Sun Hotel – Bed and Breakfast
Upon arrival in Dar es Salaam, proceed through Immigration and Customs. After exiting the Customs & immigrations Hall, Please look out for a Zoar Tours & Safari's driver/guide holding a Zoar Tours Banner with your name on it. Our Guide will assist you with your luggage and you'll be transferred to Southern Sun Hotel for overnight and relaxation. The Hotel is in the commercial centre of the city, and it borders the Botanical Gardens and diplomatic offices. The central location of the hotel makes it a perfect choice for international business travellers, NGO's and diplomats. The hotel ambience and décor would meet the approval of the founder of Dar es Salaam, the Sultan of Zanzibar, who established the city in 1882. Following in this tradition, all guests to Southern Sun Dar es Salaam are welcomed and treated like royalty. A sound rest tonight prepares us for tomorrow's adventures.
Day 02: Lake Manyara Serena Lodge – Full Board
The morning brings a change of ecosystems as we drive to the ancient soda lake of Manyara and check into the Lake Manyara Serena Lodge, standing high on a bluff above a flamingo-frosted expanse of gleaming water. The game in this petite park is plentiful and the magnificent bird watching will make a devotee out of even the most reluctant. It is also one of the very few places in Africa to see tree-climbing lions, which we may declare our day's quest, being so thoroughly sated with the big herds of preceding parks. Manyara's great shock of pink flamingoes will also delight. . From the entrance gate, the road winds through an expanse of lush jungle-like groundwater forest where hundred-strong baboon troops lounge nonchalantly along the roadside, blue monkeys scamper nimbly between the ancient mahogany trees, dainty bushbuck tread warily through the shadows, and outsized forest hornbills honk cacophonously in the high canopy. Contrasting with the intimacy of the forest is the grassy floodplain and its expansive views eastward, across the alkaline lake, to the jagged blue volcanic peaks that rise from the endless Maasai Steppes. Large buffalo, wildebeest and zebra herds congregate on these grassy plains, as do giraffes – some so dark in coloration that they appear to be black from a distance. Inland of the floodplain, a narrow belt of acacia woodland is the favored haunt of Manyara's legendary tree-climbing lions and impressively tusked elephants.
Day 03: Serengeti Serena Lodge – Full Board
After breakfast we will drive through the agricultural and fresh produce market town of Mto Wa Mbu, which is situated next to the entrance of the Lake Manyara National Park. The town is a souvenir hunters paradise, harbouring thousands souvenir salesmen - ready to pounce at your slightest invitation.Lake Manyara National Park is one of Tanzania's most dramatically located wildlife areas, consisting of a shallow soda lake (covering two-thirds of the park), located at the foot of the Great Rift Valley's western escarpment. The park's varied habitat attracts a wide variety of animals, including one of Africa's largest concentrations of elephants, Manyara's famous tree-climbing lions, as well as large flocks of flamingos, attracted by the algae in the lake.We will enjoy lunch before we head towards the Serengeti National Park via the beautiful high lying farmland of Karatu and the Ngorongoro Conservation Area. Leaving the highlands behind, we descend into the heart of wild Africa with endless plains, which roll into the distance as far as the eye can see. We spend 3 days in this incredible untamed wilderness of the Serengeti National Park, where literally millions of animals roam. We will enjoy a late afternoon game drive en route to the lodge.
We do an after breakfast game viewing drive along the Sogore River Circuit, which loops into the plains south of the Seronera River, and which is good for possible Lion, Thomson gazelle, topi, ostrich and cheetah sightings. The Visitor Centre close to the Serengeti Seronera Lodge and public campsites, is well worth a visit after the morning's game drive. This nicely designed centre offers some interesting wildlife displays as well as a gift shop selling information leaflets and maps of the area. The centre also has a shop where cold drinks and snacks can be purchased, as well as a picnic area and information trail up and around a nearby kopje. We will enjoy a relaxed picnic lunch at the centre in the shade of the giant acacia trees. In the afternoon we will follow the Kopjes Circuit, which goes anti-clockwise around the Maasai Kopjes, which usually attract a number of lion and some formidably large cobras. Kopjes are weathered granite outcrops, scattered around the plains, most of which are miniature ecosystems, providing shade and drinking water in pools left in the rock after the rains. This makes the kopjes particularly good for spotting wildlife in the dry seasons - including lions, which like to lie in wait for animals coming to drink!
Today will offer you an ideal opportunity to do an optional but unforgettable Hot Air Balloon flight, followed by a delightful champagne breakfast (available at a supplementary cost, but can be booked in advance). After breakfast we head to the south-eastern side of the park, visiting the Barafu Kopjes and the Ngare Nanyuki River area, for our morning and afternoon game drives. Apart from the lion prides you find in the area, the Barafu Kopjes is the place to visit for possible cheetah sightings. The Ngare Nanyuki River area is also well known for being packed with game.
Day 06: Ndutu Lodge – Full Board
Today is our last day in the Serengeti National Park. We will once again visit some kopjes on our way out of the park and will do a morning game drive in the Simba Kopjes area. The kopjes are named after the lions, which frequently use these kopjes to just lie and bath in the sun. You may also see baboon, giraffe and some interesting birds in this area. From here we will head to Lake Ndutu, which is alkaline, like most of the other Rift lakes, however still drinkable and used by a wide array of local wildlife. We will do an afternoon game drive in the lake area, which offers quite a change from the vast open plains of the Serengeti. The area is usually heavy populated with elephant and birds as well as resident plains game. The Ndutu Lodge is a charming small safari lodge, which is used as a base by many wildlife film crews.
Day 07: Ngorongoro Serena Lodge – Full Board
After an early breakfast we descend 600m into this stunning crater to view wildlife for a full-day's tour. You will witness an unforgettable spectacle of African wildlife - a world teeming with animals. Supported by a year round water supply and fodder, the park supports a vast variety of animals, which include herds of wildebeest, zebra, buffalo, eland, warthog, hippo, giant elephants and a small population of black rhino. Another big draw to this picturesque park is it dense population of predators, which include lions, hyenas, jackals, cheetahs and the ever elusive leopard, which sometimes requires a trained eye to spot. We will return to the lodge for lunch and spend the afternoon at leisure.
Day 08: Departure
The day starts with early morning walking safari with guide and armed ranger there after return back to lodge for breakfast, drive back to Dar es Salaam with a packed lunch. END OF SERVICE
Safari" alt="Birding Safari"/> Safari" alt="Country Based Safari"/>

redpajama_set_name: RedPajamaCommonCrawl


Spring is in the air. The subtle whiff of fresh blooms and burst of colors from yellow poinciana, red gulmohur, dazzling golden showers or laburnums, gorgeous purples of Queens's crape Myrtle and brilliant multi-colored bougainvilleas dot the landscape around. It's time for new beginnings, say the spanking new leaves in varying shades, from delicate blush to glistening greens - a treat to the senses after the rather mild and dry Mumbai winters.
The green cover that residents of the city enjoy is all the more delightful with the onset of spring hues. If only the local town-planner knew that he was being blessed and cursed in turns over his casual decision to plant random trees along some streets and on dividers, he might have paid more attention to that matter. Planting silk cotton trees sprouting gorgeous pink blooms was not one of his good ideas. These pink blooms eventually give way to pods that pop open to liberate fluffy bursts of fine cotton flying all over the place, considerately inflicting you with allergies or settling all over your clothes and hair making you look more like plucked chicken than the dapper person you started out as.
Here I am dithering about the vagaries of town-planning while for the bustling mami visiting me, the colors of spring are but distractions that take away her focus from the prime catch of spring!
So you see, mami was very plainly distressed one fine morning as I took her on a drive to show her the sights and smells of our city. And what triggered that?
It was the sight of clusters upon clusters of those delectable, slender morsels of gastronomic ecstasy - moringas or drumsticks swaying, callously ignored at a road divider. Her sudden screech on spotting them had me slamming the brakes with a palpitating heart!
"What, what, what?" I exclaimed while mami mutely pointed to the sight in front of her. Tantalizingly low hung branches laden with willowy clusters of healthy drumsticks!
In a daze of disbelief she asked, "Doesn't anybody want them?"
"Hmm...," I glanced up at what she was looking at and shrugged, more keen to start up the car and zoom on before the irate honking behind my stalled car got worse.
"How can people just let all that bounty go waste?" she lamented.
"Don't tell me people here don't make drumstick sambar? Your mama will give me no rest unless I add the flavorsome sticks everyday in some form! And moringa leaves, they are the super-food world over, didn't you know?" Mami is this vigilante types you see, keeping track of all these Whatsapp forwards on health and holistic living and a dedicated follower of every imaginable Facebook page dedicated to anything food-related.
"Well, quite honestly I never noticed till your scream gave me a heart attack over them! So I am guessing no one else did too."
"But isn't that like a sheer waste? You know ma, they cost a bomb in the market and that too for scrawnier versions of what we saw! Tch, tch, what a waste, what a waste! Do you happen to have a long stick in your car's dicky?" she asked hopefully.
"Of course not!" I replied and hurried on, keeping an eye open for all drumstick trees that might lead to future shrieks, and she failed me not. Every moringa tree we passed, she shrieked without fail.
Little did I know that I had to be wary of other botanical diversions as well!
"Aiyyo, Ramachandra!" Mami gasped. I swear she was close to convulsions. But I'd been on that path earlier so I didn't brake instantly, simply swerved the car carefully to the left and parked.
"Now what is it mami?" I looked around and didn't spot a single long stick dangling from any tree.
But I espied what had arrested her attention this time. Bunches upon bunches of tiny raw mangoes or vadus as we call them, gently swaying and casting a luscious fragrance from a mango tree, again bang on a road divider. The road beneath the tree was liberally littered with fragile vadus fallen from the tree now squashed by speeding vehicles. Street urchins and peddlers who abounded traffic signal junctions had probably bypassed raiding this tree since it was in the middle of a high speed lane.
"Do you know how difficult it is to lay your hands on good vadus? I have to scour the markets from February and plague my regular vendor to keep aside 3 kilos of the smallest vadus for me and still I get saddled with overgrown, withered ones! See, these vadus lying here are just the right size, not too big, not too small, so tender...," and she went into raptures gushing over the merits of the right vadu size for the perfect maavadu or vadu manga (not to be confused with Japanese comics - mangas) that she annually churns out from her kitchen besides every imaginable kind of pickle one can make!
"Can we go pick some out, it is such a shame to let them go waste like this!" she pleaded.
I firmly dragged her back into the car, refusing to give in to her pleas. I conceded with, "I'll take you to the sabzi market later, I am sure you'll get buckets of vadus to your liking," while fervently hoping this would be true.
Yes, spring marks the onset of the mango pickle-making ritual for mami.
It starts off with vadu mangai and moves on to the spicy hot blaze of avvakai, made in different batches - the traditional Andhra style with gingelly oil, the north-Indian style made with mustard oil and the trendier lot made with olive oil for export to folks living abroad.
In between turning over the pickle maturing in jumbo ceramic jars or barnis, mami finds it ridiculous to have meals devoid of any pickle simply because the new batch of avvakai is not ready!
According to her precise calculations they will mature reasonably only after three weeks of steeping in the tried and tested blend of oil, salt and spices, no preservatives added. In the meantime, quick-fix urgais or pickles like manga thokku, manga curry or molaga manga, will reign over the dinner table.
Summers are not to be wasted bawling over the insane intensity of the sun. Instead mami prays the sun shines brighter over her home-made vadams, appalams and mor milagais laid out to sun-dry on the scorching building terrace. By the time she is satisfied that these fritters are properly toasted, the rest of her menagerie including mama, the maid and any of the kids/grandkids popping over for the vacation, get a proper tan of the third-degree kind while keeping watch to shoo away birds from pecking at the spread.
Conferring with neighboring cronies she ensures her larder is stocked with the kiddie favorite chunda and lip-smacking aam panna for a good measure of mango overdose.
No sir, you do not dawdle and waste precious sunshine. You may not make hay but there's lots more to do while the sun shines! If mami sees her entertainment diary bereft of any festivals, she believes it makes sense to use that time to stock up on all these meal staples. Staples that could raise your BP if you just knew how much salt went into them!
Spring is the time for mami to wrap her saree pallu tightly around the waist and gear up for some extra action on the kitchen front!
I am on my way to mami's to pick up the season-special jar of mavudu that she modestly claims is her best batch yet! Drooling in anticipation....!!
Oh, I didn't mention what happened when mami spotted the coconut tree-lined street divider, did I?
Another time maybe, till later, vanakkam!
mami: Refers to a respectful address used for any Tamilian lady (typically TamBrahm) acquaintance, something like the ubiquitous Auntyji though it literally translates to mother's bro's (mama's) wife, mami.


The U.S. Department of Energy Solar Decathlon is a collegiate competition of 10 contests that challenge student teams to design and build full-size, solar-powered houses. The winner of the competition is the team that best blends design excellence and smart energy production with innovation, market potential, and energy and water efficiency.
Solar Decathlon is more than a competition. It's an intensive learning experience for consumers and homeowners as they experience the latest technologies and materials in energy-efficient design, clean energy technologies, smart home solutions, water conservation measures, electric vehicles, and sustainable buildings.
Collegiate teams spend almost two years designing and building energy-efficient houses powered by the sun. In the final competition, the teams and their houses go head to head in 10 contests to determine an overall winner.
For the first time in the event's history, teams are eligible for cash prizes. Each team that successfully builds a solar house at the competition site will receive at least $100,000 for rising to the challenge, and top finishers will receive significantly more.
Task Completion Teams complete tasks that simulate modern living. They perform household chores such as cooking and doing laundry. They host dinner parties and game nights for fellow competitors. And, they are required to log miles driving an electric vehicle charged by the house's solar electric system.
Monitored Performance Team houses and appliances perform to specified criteria, such as maintaining indoor temperature and humidity within a tight range, ensuring refrigerators maintain appropriate temperatures, and carefully controlling the flow of electricity between the house and the utility.
Jury Evaluation Jurors who are experts in fields, such as architecture, engineering, homebuilding, water use and reuse, and communications, award points for features that cannot be measured, such as aesthetics, design inspiration and innovation.
Contests based on task completion or monitored performance are called measured contests; contests based on jury evaluation are call juried contests.


Bartenieff Fundamentals address optimizing the supportive relationship between body organisation and movement intention. It incorporates fundamental principles and specific movement sequences. We will explore our Moving Self in dance through the lens of these principles such as Breath Support, Dynamic Alignment, Core Support, Axis of Length, Body Level Phrasing, Rotation and Spatial Intent. Each concept will be presented through simple experiential movement platforms that awaken the body's attention and wisdom to its functional anatomy and presence in space.
With embodied knowledge of these principles we can track our personal movement preferences more clearly. While the patterns each of us have developed may serve us well at times, we may also wish to have more choices in how we operate. Through experiencing new pathways and possibilities of how to support our bodies, we can find new ways to move in efficient and balanced ways.
In this Workshop we will approach the goal of Bartenieff Fundamental which is to move with ease, efficiency and expression. Body- and self-awareness will be enhanced, we will reflect on the inner as well as the outer process of movement experience.
In this workshop we will approach the goal of Bartenieff Fundamentals wich is to move withers efficiency and expression. Body and self-awareness will be enhanced, we will reflect on the inner as well as the outer process of movement experiencefocus on experiencing these patterns along the developmental progression, but also look into therapeutic themes that relate to each of them.
Katharina Conradi: Certified Movement Analyst, Master Dance Therapy and Registered Somatic Movement Educator and Therapist.


This seems to be a great opportunity for traditional design practitioners such as architects, visual , and industrial designers to learn about interaction design.
TorCHI is inviting people to a sneak peek of Ian Hooper and John Schrag's Design Essentials for Non-Designers tutorial at the UPA conference in June. To help them prepare for the event, they are inviting the local UX and HCI community to come in and participate, at no cost, to do a "dry-run" of the tutorial in Toronto on Friday, May 23rd.
Benefit to you: You can be in the tutorial without flying to Baltimore and paying an extra $500.
This session is intended for practitioners who have come to interaction design from a research, psychology, information architecture, or other non-design background. It focuses on what happens after the requirements are done and before you build your first prototype. Design fields such as graphic arts, architecture, and industrial design have long-standing practices for innovative design, and these apply well to interaction design.
Participants are expected to have basic knowledge and skills in usability research and evaluation practices, including requirements gathering and conducting a usability test, as none of these topics will be covered. No design background or artistic skills of any kind are necessary, but you should be able to operate a pencil.
Learn how to adapt traditional innovation practices to the design of user interfaces.
Learn useful techniques to access their creativity, and to foster innovation during the design process.
Actively participate in an interaction design process that bridges the gaps between requirements gathering, usability testing, and design iteration.
Get a list of useful references and resources.
If you would like to participate, please send John an email at <John.Schrag@autodesk.com>. A limited number of places will be available.


Tobi Stoner pitched two-hit ball over seven innings, but Josh Stinson could not finish the deal, allowing three runs on four hits in the eighth. Stoner allowed just two singles and an unearned run while walking three and striking out four.
Eric Campbell (2-4, HR(3), RBI) hit his third home run of the season, a solo shot in the seventh inning to tie the game up at 1-1.


I'm trying not to think about the fact that this little dude is an entire three months old as of Saturday because it kind of makes me want to cry. It's unfair just how short the newborn stage is. One day you're snuggling your itty, bitty brand new baby and then BAM; you're struggling to carry your three month little chunker around in his car seat. Eli really has been a dream baby though. I mean yes, he does fuss a lot usually in the evenings but for the most part he is a pretty content little guy. I wouldn't say it's been night and day difference between him and Nate but Nate was definitely harder to handle in his first three months of life. I mean, I was also a first time mom and adjusting to that with a colicky baby would make anyone crazy and even though there have been times with Eli that I've thought I couldn't handle any more of his crying; I have found that I'm more relaxed this time around.
So what's Eli like now at three months old? Well….


Although the road to self-driving cars is still a long way off, competition between Tesla, Google, Samsung, Intel and more has kept the technology steadily moving forward. In an unexpected move, Apple seems to be taking a step back from its efforts, cutting more than 200 employees from its very own Project Titan amid a restructure.
Apple has been working on its own autonomous vehicles for the past five years, at one point hitting heights of approximately 5,000 employees contributing to development in some way. Reportedly headed by Ford veteran Bob Mansfield, the company hasn't had the easiest time after a data breach came to light mid-way through last year.
Former employee Xiaolang Zhang found himself formally charged by the FBI for supposedly stealing up to 40GB-worth of data on Project Titan. He denied accusations that he planned to sell the data to a Chinese car manufacturer in an attempt to avoid a $250,000 (£189,000) fine and a jail sentence as high as 10 years. No new information has come to light since this development.
Despite poaching many of Tesla's alumni, such as engineering VP Doug Field and designer Andrew Kim at the end of last year, development seems to have come to a halt. In an interview with CNBC, Apple states that it "continues to believe there is a huge opportunity with autonomous systems" and that this is just a result of restructuring under new leadership, but this does not instil confidence that the iPhone maker is serious about the technology.
Other employees outside of the 200 that have been made redundant will remain at Apple, moving to other areas outside of Project Titan. It isn't certain when development on the project will continue, if it will carry on at all.
KitGuru Says: Hopefully this doesn't set a precedent for others to stagnate or drop autonomous efforts entirely, as Apple is a big player in the field and carries a lot of influence.


NARRATIVE: On the morning of 12/21/09 the Spokane City Fire Department responded 2 Engine companies 1 Pumper Ladder, 1 Senior Ladder, 1 heavy Rescue truck and 2 Battalion Chiefs to 5919 North Atlantic. PL 13 arrived on scene and reported that smoke was showing from under the eves of a 1 story 1200 square foot house. E3 was assigned to interior fire attack while the crew on Pl 13 was split into two teams. Team A was assigned to search the interior and team B was sent to the roof to provide ventilation to release the hot smoke and gases .Other companies were assigned to the incident as they arrived.
Quick action by arriving companies resulted in a fast extinguishment of the fire. The fire was confined to the kitchen and smoke damage throughout. The fire was declared out in about 20 minutes. There were no reported injuries and no one was found during the search. The house was vacant and the cause if this fire is under investigation.
PROBABLE CAUSE: This is under investigation.
DAMAGE EXTENT: The interior of the house had extensive damage to the kitchen and smoke damage throughout.
P.S. The Local has endorsed Greg Haff.


text:
package com.github.pocmo.sensordashboard.Server;

import android.os.AsyncTask;

import org.json.JSONArray;
import org.json.JSONException;
import org.json.JSONObject;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.net.HttpURLConnection;
import java.net.URL;
import java.net.URLEncoder;
import java.util.ArrayList;
import java.util.HashMap;

/**
 * Created by Bae Somi on 2016-11-27.
 */
public class MovingWeekData {

    String myJSON;

    private static final String TAG_RESULTS = "result";
    private static final String TAG_DATE = "timestamp";
    private static final String TAG_COUNT = "step_count";

    JSONArray userInformation = null;
    ArrayList<HashMap<String, String>> movingWeek;

    public MovingWeekData() {
        movingWeek = new ArrayList<HashMap<String, String>>();
        downloadFromDB("test3");
    }

    public ArrayList<HashMap<String, String>> getDataList() {
        movingWeek.clear();
        getData();
        return movingWeek;
    }

    protected void getData() {
        try {
            // while (myJSON==null);

            JSONObject jsonObj = new JSONObject(myJSON);
            userInformation = jsonObj.getJSONArray(TAG_RESULTS);

            for (int i = 0; i < userInformation.length(); i++) {
                JSONObject c = userInformation.getJSONObject(i);
                String date = c.getString(TAG_DATE);
                String stepcount = c.getString(TAG_COUNT);

                HashMap<String, String> info = new HashMap<String, String>();

                info.put(TAG_DATE, date);
                info.put(TAG_COUNT, stepcount);

                movingWeek.add(info);
            }

        } catch (JSONException e) {
            e.printStackTrace();
        }
    }

    public void downloadFromDB(final String userID) {
        class downloadFromDBJSON extends AsyncTask<String, Void, String> {

            @Override
            protected void onPreExecute() {
                super.onPreExecute();
            }

            @Override
            protected String doInBackground(String... params) {

                BufferedReader bufferedReader = null;
                try {
                    String link = "http://52.78.246.112/moving_week.php";

                    String data = URLEncoder.encode("USERID", "UTF-8") + "=" + URLEncoder.encode(userID, "UTF-8");
                    //String uri = params[0];

                    URL url = new URL(link);
                    HttpURLConnection con = (HttpURLConnection) url.openConnection();
                    StringBuilder sb = new StringBuilder();

                    con.setDoOutput(true);
                    OutputStreamWriter wr = new OutputStreamWriter(con.getOutputStream());

                    wr.write(data);
                    wr.flush();

                    bufferedReader = new BufferedReader(new InputStreamReader(con.getInputStream()));

                    String json;
                    while ((json = bufferedReader.readLine()) != null) {
                        sb.append(json + "\n");
                    }
                    myJSON = sb.toString().trim();

                    return sb.toString().trim();

                } catch (Exception e) {
                    return null;
                }
            }

            @Override
            protected void onPostExecute(String result) {
                super.onPostExecute(result);
                //myJSON = result;
                //getData();
            }
        }
        downloadFromDBJSON task = new downloadFromDBJSON();
        try {
            task.execute(userID).get();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

redpajama_set_name: RedPajamaGithub


NOTE: If you want to contact NASCAR or any NASCAR driver/team I cannot help you. As stated in the footer of this web site, Fantasy Racing Cheat Sheet is not owned, affiliated or sanctioned by NASCAR. I am simply an uber fan.
As noted several times before you complete checkout, you have two opportunities to self-activate your subscription.
As soon as you complete checkout you are shown a link to self-activate your subscription.
Immediately following checkout you are emailed a link to self-activate your subscription.
I get a copy and will check to be sure you self-activated before I archive it, but I know that when I pay for something, I want it right away. You're probably the same.


A traditional objection to static typing is that it has much syntactic overhead. Scala alleviates this by providing type inference.
The classic method for type inference in functional programming languages is Hindley-Milner, and it was first employed in ML.
Scala's type inference system works a little differently, but it's similar in spirit: infer constraints, and attempt to unify a type.
That one probably blew your mind. Now if you assign a type to the instantiation that is different to the variable type, you'll have problems. You may want to take time after this koan to compare and contrast with the previous one.
So, how do we get to set a Fruit basket to an Orange basket? You make it covariant using +. This will allow you to set the container to either a variable with the same type or parent type. In other words, you can assign MyContainer[Fruit] or MyContainer[Citrus].
//val navelOrangeBasket: MyContainer[NavelOrange] = new MyContainer[Orange](new Orange()) //Bad!
//val tangeloBasket: MyContainer[Tangelo] = new MyContainer[Orange](new Orange()) //Bad!
Declaring neither - nor + indicates invariance. You cannot use a superclass variable reference (contravariant position) or a subclass variable reference (covariant position) of that type. In our example, this means that if you create a citrus basket you can only reference that citrus basket with a citrus variable only.