Construction

In SFE coding, we order our alphabet $\mathcal{X}=\{ a_{1},\dots,a_{m} \}$ such that $a_{1}<\dots<a_{m}$.

We induce a lexicographical ordering (i.e. think alphabetical order like in a dictionary) on $\mathcal{X}^n$ for $n\ge2$: $$y^{n}=(y_{1},..,y_{n})<(x_{1},\dots,x_{n})=x^{n}\iff y_{1}<x_{1}$$or $\exists k\in\{ 2,\dots,n \}$ s.t. $$y_{i}=x_{i}, \ \ i=1,..,k-1\text{ and }y_{k}<x_{k}$$ and so on.

Let $p(x^{n})$ be a pmf on $\mathcal{X}^{n}$ such that $$\hat{F}(x^{n})=\sum_{y^{n}<x^{n}}p(y^{n}), \ \ {F}(x^{n})=\sum_{y^{n}\le x^{n}}p(y^{n})$$The tag of $x^{n}$ is defined as $$\bar{T}(x^{n})=\hat{F}(x^{n})+\frac{1}{2}p(x^{n})$$i.e. the midpoint of the interval $[\hat{F}(x^{n}),F(x^{n}))$.

Intuition

So by the way we define the tag we’re defining it in a way that for each $x^{n}$ in the set of messages, their tag will be inside of a disjoint interval, $[\hat{F}(x^{n}),F(x^{n}))$ from all others $x^{n}$s.