Hyperbolic Geometrically Uniform Codes and Ungerboeck Partitioning on the Double Torus

Abstract

Current research builds labelings for geometrically uniform codes on the double torus through tiling groups. At least one labeling group was provided for all of the 11 regular tessellations on the double torus, derived from triangular Fuchsian groups, as well as extensions of these labeling groups to generate new codes. An important consequence is that such techniques can be used to label geometrically uniform codes on surfaces with greater genera. Furthermore, partitioning chains are constructed into geometrically uniform codes using soluble groups as labeling, which in some cases results in an Ungerboeck partitioning for the surface. As a result of these constructions, it is demonstrated that, as in Euclidean spaces, modulation and encoding can be combined in a single step in hyperbolic space.

1. Introdution

In a typical communication system, the information to be transmitted is always subject to noise action. Despite its physical characteristics, the noise is treated by a probabilistic model by specifying the probability density function. Through this characterization, the signal to be transmitted is processed in order to control the noise action. A key component of the transmitter is the modulator. For efficient signal modulation, the modulator uses a signal constellation, which is a finite set with an appropriate geometric structure.

In particular, discrete sets of points from metric spaces that can be characterized by the existence of symmetries are of fundamental importance in the generation of signal constellations, as well as in the practical implementation of modulators and demodulators. This makes the study and investigation of these signal sets relevant in different metric spaces that inherit these algebraic and geometric properties.

It is well known that the signals of a PSK constellations of cardinality M have elements of an additive group from the ring of integers modulo as labels M, see [1]. On the other hand, the labeling of signals from a QAM constellation of cardinality M by elements of a finite group coming from a finite field appeared more directly in the works [2,3], and only by elements of an additive group G of cardinality M that need not necessarily come from a finite field, as we can see in [4].

However, labels such as these had already appeared indirectly in 1982 in [5], where Ungerboeck proposed a scheme known as trellis-coded modulation (TCM) that combines coding and modulation in a single unit, improving the noise resistance of digital transmission systems with a coding gain of 3–6 dB, without sacrificing the given information rate or requiring more bandwidth. The technique introduced by Ungerboeck is known as “mapping by set partitioning” and serves to determine the choice of modulation signals to generate coded signal sequences, i.e., codewords of a code $\mathcal{C}$, which we now call lattice code [6]. This choice is made by subsets of the constellation of signals obtained recursively in such a way that the distance between symbols is increasing.

Forney [7] proposed a practical way to encode the information bits and uncoded bits of the lattice code $\mathcal{C}$ from the signal constellations coming from the lattice ${\mathbb{Z}}^2/{\Lambda }^{\prime }$, where ${\Lambda }^{\prime }$ is a sublattice with a finite index in ${\mathbb{Z}}^2$, using the lattice partition technique.

Geometrically uniform ($GU$) codes are in deep connection with modulation. This definition was introduced by Forney in [8] and it generalized lattice codes and Slepian’s group codes [9]. This new approach meant that these two categories of codes, which had few things in common and were treated separately up to that point, were understood as part of the same code class. Moreover, $GU$ codes have good symmetry properties, such as all Voronoi regions being congruent, the signals having the same probability of error, the distance profile being the same for each signal, among others.

At the same time as [8], Loeliger [10] introduced the important concept of matched labeling. This concept creates a very suitable way to associate a set of signals with an appropriate algebraic structure. The main motivation was to provide a certain linearity to the code. His main result was to show that sets of signals matched to groups are equivalent to Slepian’s signal sets. Loeliger also proved that, under certain conditions, such concepts are equivalent.

In addition to demonstrating that many signal sets in digital communications are geometrically uniform, Forney [8] linked $GU$ codes to the Ungerboeck paper [5] by constructing geometrically uniform partitions, demonstrating that the encoder for a signal space code is given by a geometrically uniform partition and thus generalizing coset codes.

The signal constellations QAM coming from either the ${\mathbb{Z}}^2$ lattice or the ${\mathcal{A}}_2$ lattice are geometrically uniform [2,3,4]. From a geometric point of view, the signals of these constellations in ${\mathbb{Z}}^2$ and ${\mathcal{A}}_2$ can be characterized as a finite set of points coming from a set of barycenters of squares taken from a regular tessellation by squares and by a set of barycenters of regular hexagons taken from from a hexagonal tessellation, respectively.

In [11], signal constellations from the regular tessellations $\{4,4\},\{6,3\}$, and $\{3,6\}$ were built on a compact orientable surface of genus 1 (a torus) by the identification of the opposite sides of the fundamental region given by sublattices ${\Lambda }^{\prime }$ of finite index in a lattice $\Lambda$ in such a way that the torus orientation was preserved for the cases where $\Lambda ={\mathbb{Z}}^2$ and ${\mathcal{A}}_2$.

The different ways of covering the torus via regular tessellations from the ${\mathbb{Z}}^2$ and ${\mathcal{A}}_2$ lattices made it possible to introduce the technique of partitioning lattices in the construction of quantum topological codes [12,13,14,15].

Because of the good properties of $GU$ codes, several studies have been conducted in order to provide the necessary theoretical foundation and to propose generalizations so that the properties can be extended to a larger class of signal set. In addition, working in environments outside the Euclidean context has proven to be a very promising approach. In fact, certain properties of the hyperbolic space can be effectively exploited in the design of new codes.

The paper [16] was the first to propose a communication system having as its environment the hyperbolic plane. After it, several papers connecting hyperbolic geometry with communication and coding theory have been published [17,18,19,20], among others.

It is hypothesized in [21] that by constructing error-correcting codes from two- dimensional varieties with a genus of $g\ge 2$, i.e., orientable compact surfaces obtained via convenient identications of the sides of a fundamental region from a regular tessellation $\{p,q\}$ [22], it is possible to create more efficient error-correcting codes in terms of error probability.

In the hyperbolic plane, there are infinitely many regular tesselations $\{p,q\}$, while in the Euclidean plane there are only three regular tessellations: $\{4,4\}$, $\{6,3\}$, and $\{3,6\}$. From a geometric point of view, the investigation and search for geometrically uniform signal constellations obtained from finite or discrete sets given by the barycenters of polygons associated with regular tessellations $\{p,q\}$ either in the hyperbolic plane or in compact orientable surfaces obtained via convenient identification of the sides of a fundamental region of the tessellation.

In this sense, in [20], a theoretical construction was proposed to characterize the existence of geometrically uniform signal constellations in the hyperbolic plane, whose signals come from the barycenters of regular polygons associated with a regular tessellation $\{p,q\}$. For this, the complete symmetry groups $[p,q]$ of the tessellation were determined $\{p,q\}$ and proved that there are normal subgroups in $[p,q]$ using the the Reidemeister–Schreier algorithm. On the other hand, the signal constellations obtained are not identified via this technique by elements of the label group.

The works [19,23,24,25] proposed arithmetic procedures that made it possible to identify the signal constellations obtained from the barycenters of the polygons associated with families of regular tessellations $\{p,q\}$ by lattices characterized by order of quaternions that have a multiplicative R-module structure, where R is a ring of integers of a totally real number field.

The division algebra structure associated with these orders of quaternions from Fuchsian arithmetic groups provided an efficient algebraic technique in the process of combating the diversity that appears in antenna-to-antenna transmission problems. This allowed the construction of new families of space–time block codes that satisfy the property of full diversity [18,26,27].

However, the lattice structure given by the quaternion orders did not prove to be an efficient algebraic tool to characterize signal constellations that are geometrically uniform in the hyperbolic plane, precisely because of the difficulty of obtaining the group of labels, which would need to determine a suborder when seen as a group structure, as being normal in the quaternary order.

Current work arose with the objective of filling this gap, that is, to present in an explicit way the group of labels for signal constellations coming from the hyperbolic environment. Furthermore, not only are the group of labels presented, but also a systematic way of associating the group of labels with the sets of hyperbolic signals, a technique that is called signal labeling in the literature.

In order to obtain such results, a new approach was used. Instead of using quaternion algebra, the main mathematical tool was the triangular group approach. Furthermore, the current approach follows the idea in [11], where the surface genus is fixed and we work with different shapes of the fundamental region that represent the surface. In this sense, previous works invariably emphasized a certain pattern of the fundamental region for surfaces of various genres.

We follow a similar treatment for a compact surface of genus $g=2$. However, due to several differences between Euclidean geometry (the inherent geometry for the torus) and hyperbolic geometry (a geometry suitable for the construction of the double torus) and the geometric patterns of lattices in the hyperbolic case, [11] was more a source of inspiration and motivation than a basis for generalization, since the techniques in that research could not be used therein.

The hyperbolic plane, unlike the Euclidean plane, does not have a vector space structure, which makes our task of determining the group of labels for a signal constellation more difficult when we consider these signals as representing lateral classes of a quotient group $G^{\prime }=G/H$. If G denotes the symmetry group associated with signal points in the hyperbolic plane, H must be a normal subgroup in G. One of the main contributions of this work is to get around this obstacle. For this, only signal constellations coming from hyperbolic tessellations will be considered, in which, like the Euclidean tesselations, when taking the subgroup of symmetries G of the fundamental region (symmetries given by reflections), it is possible to obtain a normal subgroup H in G.

Through tiling groups, this paper presents labelings for geometrically uniform codes on the double torus. This approach provides at least one labeling group for all the 11 regular tessellations existing on the double torus, derived from Fuchsian triangular groups. We also obtain extensions of these labeling groups using involutions to generate new codes. As far as the authors are aware, it is the first time that labeling on compact surfaces with genus $g\ge 2$ has been presented in the literature.

Moreover, since all tiling groups for the double torus are soluble, all partitioning chains for $GU$ codes are performed by soluble groups of labels. The latter is an important property because the labeling groups are abelian at each level of the chain. It is important to note that the concept of soluble group is not common in communication theory, although it is deeply connected with the labeling of $GU$ codes.

Another contribution of the current paper is that, depending on the cardinality of the group of labels and their algebraic structure, Ungerboeck partitioning for the signal constellation was obtained. Accordingly, this result means an Ungerboeck partitioning for both the surface and the hyperbolic space.

2. Fundamental Concepts

In this section, we introduce the necessary concepts and definitions to establish the results of current research. We recommend [28] for details on hyperbolic geometry.

2.1. Geometrically Uniform Codes and Labeling

Let $(M,d)$ be a metric space. We denote by $ISO\left(M\right)$ the group of all isometries on M, where the operation in M is the composition. A code is any non-empty set C of M. If C is a discrete set, then it is called a signal set.

Definition 1.

A symmetry of C is an isometry u of M that leaves C invariant, $u\left(C\right)=C$. The symmetries of C form a group under composition, the symmetry group $\Gamma \left(C\right)$ of C.

Definition 2.

A signal set C is geometrically uniform ($GU$) if, given any two points x and y in C, there is an isometry $u_{xy}:M\to M$ such that $u_{xy}\left(x\right)=y$ and $u_{xy}\left(C\right)=C$. A uniform constellation is a finite $GU$ signal set of C, and a uniform lattice is an infinite $GU$ signal set of C.

Definition 3.

Given a signal set C, a subset $U\left(C\right)$ of $\Gamma \left(C\right)$ is a generator set of C if $C=\{u\left(x_0\right):u\in U\left(C\right)\}$ for a fixed $x_0$ and $U\left(C\right)$ is minimal to generate C, if the map $g:U\left(C\right)⟶C$ defined by $g\left(u\right)=u\left(x_0\right)$ is bijective.

The map g induces the group structure of $U\left(C\right)$ on C, and g can be viewed as a group isomorphism.

Another important concept associated with $GU$ codes is Loeliger’s [10] definition of signal set matched to a group.

Definition 4.

A signal set C is matched to a group $\left(G\right)$ if there is a surjective map m from G on C such that, for every g and h in G, one has $d(m\left(g\right),m\left(h\right))=d(m(g^{-1}.h),m\left(e\right))$, where e denotes the neutral element of G. An application m satisfying this condition is a matched map. If, in addition, m is injective then $m^{-1}$ is called a matched labeling.

Proposition 1

([10]). A signal set C is matched to a group G by a matched map $m:G\to C$ if and only if G is homomorphic to a transitive subgroup of $\Gamma \left(C\right)$, the group of symmetries of C.

Corollary 1

([10]). There is a matched labeling between the signal set C and the group G if and only if G is isomorphic to a transitive subgroup of $\Gamma \left(C\right)$.

In what follows, we define soluble (solvable) groups. This is a very important concept in group theory. It is not a well-known concept in communication theory, but as we will see, $GU$ codes have a close relationship with soluble groups.

Definition 5.

A group G is soluble if there exists a finite sequence of subgroups $1=G_0<G_1<\cdots <G_n=G$ such that

(1)

$G_{j-1}$ is normal in $G_j$;

(2)

$G_j/G_{j-1}$ is an abelian group, for $j=1,2,\cdots ,k$.

It must be observed that the condition $G_{j-1}⊲G_j$ does not imply that $G_j⊲G$.

2.2. Hyperbolic Geometry

Let $\mathbf{D}=\{z\in C:|z|<1\}$ be the Poincaré disk model for the hyperbolic plane, where we consider the Riemannian metric $ds=\frac{2\left|dz\right|}{1-{\left|z\right|}^2}$. We denote by $ISO\left(D\right)$ the isometry group of $\mathbf{D}$, and by $ISO{\left(\mathbf{D}\right)}^{+}$ and $ISO{\left(\mathbf{D}\right)}^{-}$ the isometry groups that preserve and do not preserve orientation, respectively.

The disc model for the hyperbolic plane was adopted in this work because it allowed a better visualization of some symmetries. However, all results may be considered for other models, such as the half-plane model $\mathbf{H}$. All geometric parameters hereinafter, such as length, area, etc., will be considered in relation to the metric $ds$. It is noteworthy that the measures of angles in D are exactly the same as those in the Euclidean case.

Definition 6.

A Fuchsian group Γ is a discrete subgroup of $ISO{\left(\mathbf{D}\right)}^{+}$. Γ is a cocompact Fuchsian group if $\frac{D}{\Gamma }$ generates a compact surface.

The terminology adopted in this paper is similar to that used in [29,30]. The details of the results and definitions in this section and in Section 2.3 can be found in [28].

By the Gauss–Bonnet theorem, it is known that the area of a hyperbolic polygon depends only on its angles.

Theorem 1

(Gauss–Bonnet). Let P be a hyperbolic polygon with p sides, vertices $v_1,v_2,\dots ,v_p$, and with inner angles ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_p$, respectively. Then, the area of P is given by

$$\mu \left(P\right)=(p-2)\pi -({\alpha }_1+{\alpha }_2+\dots +{\alpha }_p).$$

It must be observed that in Euclidean geometry, the angles of any polygon do not determine its area. This characteristic of hyperbolic geometry has a major influence on their lattices and hence on the lattices on compact surfaces with genus greater than or equal to 2. In the Euclidean plane, it is possible to obtain a multitude of lattices based on equilateral triangles of different areas, but in the hyperbolic disc, there is only one way. On the other hand, it is known that there are only three regular tessellations in the Euclidean plane (equilateral triangles, squares, and hexagons), but in $\mathbf{D}$ there are endless possibilities, and this is one of the main properties that makes hyperbolic geometry very favorable for creating geometrically uniform codes.

Theorem 2.

Γ is a Fuchsian group if, and only if, Γ acts properly discontinuously on $\mathbf{D}$.

Definition 7.

Let Γ be a group of isometries acting properly discontinuously on $\mathbf{D}$. A closed subset $\tilde{F}\subset \mathbf{D}$ with non-empty interior is a fundamental region of G if

(i)

${\bigcup }_{T\in \Gamma }T\left(\tilde{F}\right)=\mathbf{D}$ and

(ii)

$int\tilde{F}\bigcap T\left(int\tilde{F}\right)=Ø$, for all $T\in \Gamma \backslash \left\{I_d\right\}$, where $int\tilde{F}$ is the set of interior points of $\tilde{F}$.

The familly $\{T\left(\tilde{F}\right):T\in \Gamma \}$ is called a tessellation (or a tiling) of $\mathbf{D}$. The area of a fundamental region, if finite, is a numerical invariant of the group. Let $\Gamma$ be a Fuchsian group and $z_1\in \mathbf{D}$ given such that $T\left(z_1\right)\ne z_1$ for all $T\in \Gamma \backslash \left\{I_d\right\}$, then ${\Gamma }_{z_1}\left(G\right)=\{z\in \Gamma :d(z,z_1)\le d(z,T\left(z_1\right)),\forall T\in \Gamma \}$ is a fundamental region of $\Gamma$, called Dirichlet region.

There are other ways of determining a fundamental region of a Fuchsian group, such as the Ford regions. However, even if we have different polygons, the area is always the same. In this work, we used Dirichlet regions in all cases except one, in which a star polygon was used. The reason for this choice will become clear later. In the next section, we present a strong relationship between a group $\Gamma$ and its fundamental region, with compact surfaces.

2.3. Compact Surfaces and Fundamental Regions

A hyperbolic polygon P with p sides, or a p-gon, is a closed convex set consisting of p hyperbolic geodesic segments. A p-gon whose edges have the same length and its inner angles are all equal is called a regular p-gon. The p-gon is denoted by $\{p,q\}$ if the inner angles are $\frac{2\pi }{q}$ with a q integer. A tessellation of $\mathbf{D}$ by a p-gon will be called a tessellation $\{p,q\}$.

A compact superface S may be obtained from a polygon P, identifying pairs of edges, once the side and angle conditions are satisfied.

Side and angle conditions: If a compact polygon P is a fundamental region for an isometry group $\Gamma$ that maintains orientation in $S^2$ (spherical surface), ${\mathbf{R}}^2$ (Euclidean plane) or $\mathbf{D}$, then:

(i)

for each side s of P, there is a single side $s^{\prime }$ of P such that $s=\tau \left(s\right)$, where $\tau \in \Gamma$;

(ii)

the sum of the angles in each vertex of a side-pairing of P is equal to $2\pi$.

Theorem 3

(Poincaré’s Theorem). A compact polygon P, satisfying the side and angle conditions, is a fundamental region of the group Γ generated by the pairing mappings of the sides of P, and Γ is a Fuchsian group.

A maximal set of vertices $v_1,v_2,\cdots ,v_k$, identified in a side-pairing mapping, is a vertex cycle. All compact surfaces with genus $g\ge 2$ may be obtained geometrically from hyperbolic polygons.

Each non-trivial element of $ISO{\left(\mathbf{D}\right)}^{+}$ can be classified as parabolic (having no fixed point in $\mathbf{D}$ and a fixed point on the border $\partial \mathbf{D}$), elliptic (having a fixed point in $\mathbf{D}$ but no fixed point in $\partial \mathbf{D}$), or hyperbolic (having no fixed point in $\mathbf{D}$ and two fixed points in $\partial \mathbf{D}$).

Let $\Gamma$ be a Fuchsian group acting on $\mathbf{D}$ and P, a Dirichlet region of $\Gamma$. Then P has a finite number of vertices, p. These vertices are the fixed points of the elliptical elements of $\Gamma$. Consider the orders of these elliptical elements, $m_1,\cdots ,m_p$. That is, given an elliptical element $\gamma$ in $\Gamma$ there is an integer $m_{\gamma }$ such that ${\gamma }^{m_{\gamma }}=Id$, and let g be the genus of the compact and orientable surface $\frac{D}{\Gamma }$. The ordered set of integers $(g,m_1,\cdots ,m_p)$ is called the signature of $\Gamma$. If a Fuchsian group $\Gamma$ has no elliptical elements, its signature is $(g,0,\cdots ,0)$, or simply $(g,-)$. Giving $z\in \mathbf{D}$, consider $\Lambda (\Gamma )\left(z\right)$ the set of all limit points in $\mathbf{D}\bigcup \partial \mathbf{D}$ of the orbit of $\Gamma \left(z\right)$. Let $\Lambda (\Gamma )$ be the set of all $\Lambda (\Gamma )\left(z\right)$, for all $z\in \mathbf{D}$. If $\Lambda (\Gamma )=\partial \mathbf{D}$, then $\Gamma$ is a Fuchsian group of the first type. Otherwise, $\Gamma$ is of the second type.

It may be proved that the fundamental region of a compact surface with genus g has an area of $4\pi (g-1)$. In particular, we have an area of $4\pi$ for the double torus. Besides, if H is a subgroup of $\Gamma$ (denoted by $H<\Gamma$), then the area of the fundamental region of H divides the area of the fundamental region of $\Gamma$. Moreover, if p is the number of sides of the fundamental region for a group of the first type, with signature $(g,-)$, then $4g\le p\le 12g-6$ [28].

Results of [31] show that there are only four regular polygons which are fundamental regions for the double torus. These are $\{8,8\}$, $\{10,5\}$, $\{12,4\}$, and $\left\{18.3\right\}$, with 4, 6, 6, and 8 possible Fuchsian groups with signature $(2,-)$, respectively. Some non-regular cases of polygons as fundamental regions for the double torus may be found in [31].

2.4. Tiling Groups

This section is a short description of tiling and OP-tiling groups. A detailed description of the results and techniques used here may be found in [29,30].

Let S be a compact surface of genus g and G a finite group acting orientably and effectively on S. The quotient space $S/G$ is a differentiable surface, and the quotient projection $\pi :S\to \frac{S}{G}$ is a branched covering.

The paper [29] presents all groups G for compact surfaces of genus 2 and 3 using an inductive method. A complete classification for genera $g\le 13$ is given in [30]. In fact, for smaller genera, a lot of information and important results have already been established. In [30], the group G is extended to a group $G^{*}$, such that $|\frac{G^{*}}{G}|=2$, resulting in $G⊲G^{*}$. The groups $G^{*}$ and G will be referred to as tiling and OP-tiling (preserves orientation), respectively, and play an important role in labeling signal sets on compact surfaces of the genus $g\ge 2$.

The next section provides a more detailed presentation of such groups, with special attention to the cases where G is a triangular tiling group.

Tilings Groups and $GU$ Codes

We give an example to elucidate the relationship between such groups and $GU$ codes. Consider on a surface a lattice given by non-obtuse triangles, so that each reflection around the side of each one of these triangles extends to an isometry on the entire surface, preserving the lattice. Further, consider that the sides of these triangles extend to a closed geodesic on the surface formed only by the sides of the triangles. The tiling group $G^{*}$ is the group generated by these reflections.

These groups are given by isometries of S which preserve the lattice with the properties described above. Each one of these groups has an index 2 subgroup, consisting of conformal isometries which also preserve such lattices.

In the context of $GU$ codes, these groups may be used as groups of labels for suitable choices of signal constellations. In fact, given a compact surface, we consider the incenters of each triangle in a lattice as a signal constellation, determined by the characteristics described above. The tiling group associated with this lattice has the desired properties, i.e., it is a subgroup of the symmetry group of the surface; it has the same cardinality as the signal constellation and preserves the lattice. Thus, these lattices are the primary building blocks for the creation of $GU$ codes whose minimal generator groups are tiling groups and also the $OP$-tiling groups.

Definition 8.

A group of G of isometries of the hyperbolic plane is said to be of type $(\alpha ,\beta ,\gamma )$ if G is generated by reflections on the sides of a triangle with inner angles $\alpha ,\beta$, and γ. Such groups are called triangle groups or triangular groups. In particular, if $l,m$ and n are integers greater than or equal to 2, G is of type $(l,m,n)$ if G is generated from a triangle with inner angles $\frac{\pi }{l}$, $\frac{\pi }{m}$, and $\frac{\pi }{n}$.

Depending on the values of the internal angles, a triangle group is neither Fuchsian nor discrete. However, it is always possible to obtain an index 2 subgroup formed by conformal isometries from a triangle group.

In [31], all groups with a signature $(2,-)$, which admit a regular polygon as a fundamental region, are obtained. All groups are arithmetical Fuchsian groups because they are subgroups of finite index of triangular Fuchsian arithmetic groups. A complete list of triangular Fuchsian groups, containing a subgroup with signature $(2,-)$, is also shown.

However, in many cases where the group of genus 2 may be seen as a subgroup of a triangular group, its fundamental region is represented by a non-regular polygon. Some of these cases are exemplified in [31].

Interestingly, when considering compact surfaces, most searches for geometrically uniform codes in hyperbolic spaces take a regular polygon of the self-dual case $\{4g,4g\}$ as their fundamental region of the surface; in other cases, regular polygons are also taken. Because the fundamental regions for compact surfaces are frequently represented by non-regular polygons, this gives a limitation in obtaining $GU$ codes. In this case, current research is based on a more general treatment because it considers regular and non-regular polygons as fundamental regions.

As will be noted later, among the 11 cases of tiling groups (consequently OP-tiling groups), only 4 may be identified as a regular region for the double torus. The other cases are represented as non-regular regions. The following result from [31] gives the groups.

Theorem 4.

The Fuchsian arithmetical triangular groups which contains a subgroup of signature (2,-) are: $(2,3,7)$, $(2,3,8)$, $(2,3,9)$, $(2,3,10)$, $(2,3,12)$, $(2,3,18)$, $(2,4,5)$, $(2,4,6)$, $(2,4,8)$, $(2,4,12)$, $(2,5,5)$, $(2,5,10)$, $(2,6,6)$, $(2,8,8)$, $(3,3,4)$, $(3,3,5)$, $(3,3,6)$, $(3,3,9)$, $(3,4,4)$, $(3,6,6)$, $(4,4,4)$, and $(5,5,5)$.

From [32] we have the following result.

Theorem 5.

The triangle groups having a torsion free normal subgroup of genus 2 are: $(2,3,8)$, $(2,4,6)$, $(2,4,8)$, $(2,5,10)$, $(2,6,6)$, $(2,8,8)$, $(3,3,4)$, $(3,4,4)$, $(3,6,6)$, $(4,4,4)$, $(5,5,5)$. All of them are arithmetic subgroups of $SL(2,\mathbf{R})$.

The proof that these are Fuchsian arithmetical groups is given in [33]. OP-tiling groups are explicitly obtained as a group of complex matrices, for genera 2 and 3, in [34]. For the purposes of this study, the only cases in which normality occurs are those in which the labelings are performed using groups derived from the quotient $\frac{(l,m,n)}{G}$.

We will detail all the groups G for genera $2\le g\le 13$. Moreover, in each case, we consider extensions $G^{*}$ of G, thus enabling the generation of more labeling groups for a greater number of geometrically uniform constellations. OP-tiling groups are formally defined now. They are exactly the quotient groups of interests. We also have the definition of tiling groups used for labeling.

Definition 9.

Let S be a compact orientable superface with genus g. A tiling T of S is a complete non-superposing covering of S by polygons. These polygons are called tiles. The edges of the tiles are called edges of the tiling, and the vertices of the tiles are called the vertices of the tiling. We denote by V and E the family of edges and vertices of the tiling, respectively.

Definition 10.

A kaleidoscopic tiling T of a surface is one in which the local reflection in the edge e, $r_e$, is an isometry of the surface applying tiles in tiles, for each edge e of the tiling. In particular, it swaps the two tiles that have e as a common edge.

Definition 11.

A kaleidoscopic tiling T is called geodesic, if for each edge e, the set of fixed points of $r_e$, denoted by $S_{r_e}=\{x\in S:r_e\left(x\right)=x\}$, is given by a union of edges of T.

There are kaleidoscopic tilings that are not geodesic, such as, for instance, the dodecahedral tiling of the sphere by twelve pentagons. More information about this fact can be found in [30].

The reflections in relation to the edges of a tiling generate an isometry group of the tiling, which is called the Tiling Group. It can be proved that all tiles on the surface are an image, by an element of the tiling group, of one tile, which is called the “fundamental tile”. Let us consider that ${\Delta }_0$ is the main tile, with vertices $P,Q$, and R, and let us denote by $p,q$, and r the opposite sides of these vertices, respectively. We also denote by $p,q$, and r the reflections on the respective sides. Thus, due to the geodesic condition, there is the same number of equal angles around each vertex. Angles at $P,Q$, and R thus measure $\frac{\pi }{l}$, $\frac{\pi }{m}$ and $\frac{\pi }{n}$, where $l,m$, and n are integers greater than or equal to 2. Thus, it is said that ${\Delta }_0$ is a $(l,m,n)$-triangle.

It follows that $p^2=q^2=r^2=1$. Defining $a=pq$, $b=qr$ and $c=rp$, $a,b$, and c are anticlockwise rotations around the vertices of ${\Delta }_0$, with orders $l,m$, and n, respectively. Denoting by $G^{*}=<p,q,r>$ and $G=<a,b,c>=<a,b>$, G is the subgroup of $G^{*}$ generated by isometries that preserve the orientation. Therefore, G is a normal subgroup of index 2 and $G^{*}=<q>⋉G$, where ⋉ represents the semi-direct product.

Definition 12.

The group $G^{*}$ is called the total tiling group of S or simply tiling group of S. The subgroup G is called the conformal tiling group or OP-tiling group (preserves orientation).

It is important to note that there may have been isometries of S preserving the tiling which are not contained in $G^{*}$. In this case, the group of all symmetries of the tiling may be factored as $U⋉G^{*}$, where U is the stabilizer of the main tile [29].

With respect to matched labeling groups, we know they are transitive subgroups of a symmetry group. If they are groups with minimal generators, their cardinality is the same as the signal set. It follows that determining the tiling groups is the same as finding a minimal generator group for labelings on compact surfaces.

This is the main contribution of the current analysis. On compact surfaces, we show a strong relationship between tiling groups and $GU$ codes. Moreover, this study shows the geometrical representations of the fundamental regions for each group and also an adequate representation of the double torus in each case. The advantage of this approach is that it can solve all cases of triangular group labeling in compact surfaces up to genus 13.

An OP-tiling group’s triple-generating elements can always be made to satisfy the relationship $o\left(a\right)=l$, $o\left(b\right)=m$, $o\left(c\right)=n$, where $o\left(x\right)$ is the order of x, and $abc=pqqrrp=1$. That is, elements $a,b$, and c may be chosen as generators of the stabilizers of a triple of points on S. The following theorem is a particular case of the Theorem 12 from [29].

Theorem 6.

Let G be an OP-tiling group on a surface S, with generators $a,b,c$, with orders $l,m,n$ respectively. If G has an involution θ (${\theta }^2=I$), satisfying

$$\theta \left(a\right)=qa{q}^{-1}=qpqq=qp=a^{-1}and \theta \left(b\right)=qb{q}^{-1}=qqrq=rq=b^{-1},$$

then the surface has a tiling T by $(l,m,n)$-triangles, such that the OP-tiling group constructed above is the desired group G. Beyond that, the generators $a,b,c$ are generated from an initial tile, and $G^{*}\simeq <\theta >⋉G$.

2.5. The Double Torus

Table 1. Labeling Groups.

Card (G)	(l,m,n)	G
5	(5,5,5)	$Z_5=\left\{x\right|x^5=1\}$
6	(3,6,6)	$Z_6=\left\{x\right|x^6=1\}$
8	(2,8,8)	$Z_8=\left\{x\right|x^8=1\}$
8	(4,4,4)	$\langle x,y|x^4=y^4=1,x^2=y^2,y^x=y^{-1}\rangle$
10	(2,5,10)	$Z_{10}=\left\{x\right|x^{10}=1\}$
12	(2,6,6)	$Z_6\times Z_2=\left\{x\right|x^6=1\}\times \left\{y\right|y^2=1\}$
12	(3,4,4)	$D_{43-1}=\langle x,y|x^4=y^3=1,y^x=y^{-1}\rangle$
16	(2,4,8)	$D_{283}=\langle x,y|x^2=y^8=1,y^x=y^3\rangle$
24	(2,4,6)	$\langle \alpha ,\beta ,\gamma ,\delta |{\alpha }^2={\beta }^2={\gamma }^2=[\beta ,\gamma ]=[\beta ,\delta ]=[\gamma ,\delta ]=[\beta ,\alpha ]=1,{\gamma }^{\alpha }=\gamma \beta ,{\delta }^{\alpha }={\delta }^{-1}\rangle$
24	(3,3,4)	$S{L}_2\left(3\right)=\langle x,y|x=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right),y=\left(\begin{array}{cc}0& 1\\ -1& 0\end{array}\right)\rangle$
48	(2,3,8)	$G{L}_2\left(3\right)=\langle x,y|x=\left(\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right),y=\left(\begin{array}{cc}-1& 1\\ -1& 0\end{array}\right)\rangle$

shows the 11 cases of OP-tiling groups G that are the quotient of a triangular group with a normal subgroup of order 2. All of them are kaleidoscopic, which means that they can be extended by an involution to have the tiling group $G^{*}$, doubling the number of lattices on the double torus, which will be geometrically uniform and have the labeling group $G^{*}$.

Further, all these tiling groups are soluble, which is quite an interesting fact because it allows uniform partitions of the codes. Moreover, the labels for the partitions will be by Abelian groups. It is noteworthy that, in larger genera, it is not always possible to extend G to $G^{*}$, i.e., the tilings are not kaleidoscopic, and, in other cases, even if the tiling is kaleidoscopic or not, it may not admit a soluble chain. The good behavior of the tilings on the double torus will be explored in detail in the last section. A table with matrix groups similar to Table 1 may be found in [34].

3. Signal Constellations on the Double Torus by Tiling Groups

In this section, we will look at the OP-tiling groups G and their extensions $G^{*}$ one by one. Fundamental regions will be presented for groups G and $G^{*}$, together with the respective matched labelings. The genus 2 group is denoted by ${\Pi }_2$, and the fundamental regions of ${\Pi }_2$, G, and $G^{*}$ are denoted by $P_2$, $P_G$, and $P_{G^{*}}$, respectively. Besides, the geometrically uniform signal constellations on the hyperbolic polygon representing the double torus, denoted by C, will be given by the centers (incenters) of the fundamental regions of $P_G$ and $P_{G^{*}}$.

In some cases, there are two or more possibilities to represent the fundamental regions of the groups inside the fundamental region of the double torus. However, this does not alter the labeling groups. What changes is just how to view them. For the labeling of regions, a point to represent the neutral element of labeling group must be chosen. Henceforth, the other points are determined by the algebraic and geometric properties of these groups. In all cases, $\frac{(a,b,c)}{{\Pi }_2}\simeq G$ is a normal subgroup of $G^{*}$.

(Case 1) ${\Pi }_2⊲(5,5,5)$

Group $(5,5,5)$ has a normal subgroup ${\Pi }_2$ with index 5. It follows that $\frac{(5,5,5)}{{\Pi }_2}\simeq G=Z_5$ and that $P_G$ divides $P_2$ into 5 congruent regions. A tessellation on the double torus is determined so that, when considering the center of these 5 congruent regions as the signal set C, we have $Z_5$ as the labeling group for C.

In this case, the fundamental region $P_2$ is the regular polygon $\{10,5\}$. The fundamental region $P_G$ is a four-sided polygon with the same length and inner angles that alternate between $\frac{\pi }{5}$ and $\frac{2\pi }{5}$, whereas the fundamental region $P_{G^{*}}$ is is the triangle $\{3,10\}$. Tessellations on the flat torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 1a,b.

(Case 2) ${\Pi }_2⊲(3,6,6)$

${\Pi }_2$ is a normal subgroup of $(3,6,6)$ with index 6. Table 1 shows that $\frac{(3,6,6)}{{\Pi }_2}\simeq G=Z_6$, i.e., the fundamental region of the double torus $P_2$ is subdivided into six congruent regions, any of which can be used as a fundamental region for G.

In this case, the fundamental region for ${\Pi }_2$ is a semi-regular 12-gon, with equal sides and inner angles, alternating between $\frac{2\pi }{3}$ and $\frac{\pi }{3}$. The fundamental region for G is the regular polygon $\{4,6\}$ and the fundamental region for $G^{*}$ is the triangle $(3,6,6)$. Tessellations on the flat torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 1c,d.

(Case 3) ${\Pi }_2⊲G=(2,8,8)$

${\Pi }_2$ is a normal subgroup with index 8 of $(2,8,8)$. Table 1 shows that $\frac{(2,8,8)}{{\Pi }_2}\simeq G=Z_8$, i.e., the fundamental region of double torus group is subdivided into 8 congruent regions that are fundamental regions for G.

The fundamental region for ${\Pi }_2$ in this case is the regular polygon $\{8,8\}$, which is the only one that generates a self-dual tessellation for the double torus. The fundamental region for G is the triangle $(4,8,8)$ and the fundamental region for $G^{*}$ is the triangle $(2,8,8)$. The tessellations on the flat torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 1e,f.

(Case 4) ${\Pi }_2⊲(2,5,10)$

${\Pi }_2$ is a normal subgroup with index 10 of $(2,5,10)$. Table 1 gives that one has $\frac{(2,5,10)}{{\Pi }_2}\simeq G=Z_{10}$, i.e., the fundamental region of the double torus group is subdivided into 10 congruent regions that are fundamental regions for G.

In this case, as in the first one, we have the regular polygon $\{10,5\}$ as a fundamental region for ${\Pi }_2$. Groups G and $G^{*}$ have as fundamental regions the triangle $(5,5,10)$ and the triangle $(2,5,10)$, respectively. Tessellations on the flat torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 1g,h.

The first four cases are all labelings in which G is Abelian, and more specifically, cyclic.

(Case 5) ${\Pi }_2⊲(4,4,4)$

${\Pi }_2$ is a normal subgroup with index 8 of $(4,4,4)$. Table 1 displays $\frac{(4,4,4)}{{\Pi }_2}\simeq G=Q_2$, the quaternion group of order 8. This is a non-Abelian group of lower order, such that all its subgroups are normal. In this case, as in case 3, one has the regular polygon $\{8,8\}$ as a fundamental region for ${\Pi }_2$.

$P_{G^{*}}$ is the triangle $\{3,8\}$, whereas G has a quadrilateral with equal sides and inner angles that alternate between $\frac{\pi }{4}$ and $\frac{\pi }{2}$ as its fundamental region. Tessellations on the flat torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 2a,b.

The method presented in this paper to create labeling on the double torus does not exhaust all the possibilities for labeling, not even by triangular groups, as observed in the above remark. It presents a systematic way to find at least one labeling for each case, where group ${\Pi }_2$ is a normal subgroup of a triangular group.

(Case 6) ${\Pi }_2⊲(2,6,6)$

${\Pi }_2$ is a normal subgroup of $(2,6,6)$ with an index of 12 in this case. Table 1 displays $\frac{(2,6,6)}{{\Pi }_2}\simeq G=Z_6\times Z_2$.

Then, $P_2$ is a semi-regular 10-gon with equal edges that is formed by joining two regular polygons $\{6,6\}$. The fundamental region for G is the triangle $(3,6,6)$ and the fundamental region for $G^{*}$ is the triangle $(2,6,6)$. The tessellations on the double torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 2c,d.

(Case 7) ${\Pi }_2⊲(3,4,4)$

In this case, $P{i}_2$ is a normal subgroup of $(3,4,4)$ with index 12. Table 1 shows $\frac{(3,4,4)}{{\Pi }_2}\simeq G=D_{4,3,-1}$.

Thus, the fundamental region for ${\Pi }_2$ is a 12-gon, with inner angles of $\frac{\pi }{2}$, and edges with lengths in the form $(l,l,2l,l,l,2l,l,l,2l,l,l,2l)$, where l is the length of the side of triangle $(3,4,4)$, which is between the angles $\frac{\pi }{4}$ and $\frac{\pi }{4}$. The fundamental region for G is a polygon with four edges with inner angles equal to $\frac{\pi }{4},\frac{\pi }{2},\frac{\pi }{4}$ and $\frac{2\pi }{3}$, and the fundamental region for $G^{*}$ is the triangle $(3,4,4)$. Tessellations on the flat torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 2e,f.

(Case 8) ${\Pi }_2⊲(2,4,8)$

In this case, $\frac{(2,4,8)}{{\Pi }_2}\simeq G=D_{2,8,3}$, with order 16. The 8-gon $\{8,8\}$, the triangle $(4,4,4)$, and the triangle $(2,4,8)$ are the fundamental regions $P_2,P_G$, and $P_{G^{*}}$, respectively. Tessellations on the flat torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 2g,h. $P_2$ can also be represented by the edge-by-edge combination of two 8-gons $\{8,4\}$, yielding a 14-gon.

(Case 9) ${\Pi }_2⊲(2,4,6)$

$\frac{(2,4,6)}{{\Pi }_2}\simeq G=\langle x,y,z,w|x^2=y^2=z^2=1,w^3=1,z^x=zy,w^x=w^{-1}$ and Abelian relations $\rangle =\langle 4,6|2,2\rangle$, with order 24.

This group and its geometrical construction from a hyperbolic tessellation is described in detail by Coxeter and Moser in [35]. The authors found a fundamental region for the double torus in the form of a star polygon and deducted a presentation for G using two generators, namely $G=\langle r,s|r^4=s^6={\left(rs\right)}^2={\left(r^{-1}s\right)}^2=1\rangle$. The same representation was also used in [34]. We adopted the presentation given in [35], in which only two generators are used, as in previous cases, to label the constellation of this case. Another reason is that the generated fundamental region $P_2$ appears as a star polygon. This is a property that has not been reported in previous works on $GU$ codes in hyperbolic spaces.

The fundamental region $P_2$ is a star 12-gon with inner angles, alternating between $\frac{\pi }{3}$ and $\frac{2\pi }{3}$ and equal sides, each measuring twice the side between the angles $\frac{\pi }{2}$ and $\frac{\pi }{6}$ of the triangle $(2,4,6)$. Regions $P_G$ and $P_{G^{*}}$ are a triangle $(2,4,6)$ and a quadrilateral with inner angles $\frac{\pi }{2}$, $\frac{\pi }{2}$, $\frac{\pi }{2}$ and $\frac{\pi }{6}$, respectively. Tessellations on the double torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 3a,b.

(Case 10) ${\Pi }_2⊲(3,3,4)$

$\frac{(3,3,4)}{{\Pi }_2}\simeq G=S{L}_2\left(3\right)$ in this case. The fundamental regions for $P_G$ and $P_{G^{*}}$ are a 4-gon with inner angles $\frac{\pi }{3},\frac{\pi }{4},\frac{\pi }{3}$, and $\frac{2\pi }{3}$ given by the union of two adjacent triangles $(3,3,4)$ and the triangle $(3,3,4)$, respectively.

The region $P_2$ is a 16-gon with edges measuring $(2l,2l,l,l,2l,2l,l,l,2l,2l,l,l,2l,2l,l,l)$, where l is the length of the side between the angles $\frac{\pi }{4}$ and $\frac{\pi }{3}$ of triangle $(3,3,4)$. The inner angles measure $\frac{2\pi }{3}$ in the vertices between sides $2l,2l$ and $2l,l$, and $\frac{\pi }{2}$ in the vertices between sides $l,l$. Tessellations determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 3c,d.

(Case 11) ${\Pi }_2⊲(2,3,8)$

In this case, $\frac{(2,3,8)}{{\Pi }_2}\simeq G=G{L}_2\left(3\right)$. The fundamental region $P_2$ is a 10-gon with equal sides, measuring $2m+2n$, where m is the measure of the side between the angles $\frac{\pi }{8}$ and $\frac{\pi }{3}$, and n is the measure of the side between angles $\frac{\pi }{3}$ and $\frac{\pi }{2}$, both in the triangle $(2,3,8)$.

The regions $P_G$ and $P_{G^{*}}$ are, respectively, triangles $(3,3,4)$ and $(2,3,8)$. Tessellations on the flat torus determined by $P_G$ and $P_{G^{*}}$ are shown in Figure 3e,f.

4. Geometricaly Uniform Partitions and Hyperbolic Ungerboeck Labeling

Ungerboeck in [36,37] introduced the concept of application by set partitioning. In this concept, a code for the signal space is defined by a partition of the signal set into subsets, a labeling of these subsets, and a labeling code that specifies the sequence of subsets via a sequence of labels.

Forney [8] generalized these ideas and showed that this concept was the same as determining normal subgroups for a minimal generator set, associated with certain signal subsets from the sets of geometrically uniform signals. The natural labeling for signal partitions in this case is given by a set of labels that is isomorphic to the quotient group $U\left(C\right)/U^{\prime }$.

Even when working with general definitions and theorems, Forney focused his approach on cases where the partitioning labeling group is isomorphic to ${Z_2}^n$. The author remarked that further studies on the algebraic properties of labeling groups were needed.

Because $G^{*}$ is always soluble in the double torus, it is possible to extract Abelian, eventually cyclic, labels for each case. It is also possible, in some situations, to build labelings that are isomorphic to ${Z_2}^n$. We have the following result.

Theorem 7.

The only cases that are isomorphic to the group $Z_2^n$ are $(2,8,8)$, $(4,4,4),$ and $(2,4,8)$.

Proof. 

If the group cardinality is not a power of 2, then the group cannot be isomorphic to $Z_2^n$. This excludes all other groups as candidates to be isomorphic to $Z_2^n$. Analyzing the cases $(2,8,8)$, $(4,4,4)$, and $(2,4,8)$, we note that they have a cardinality that is a power of 2, so they are candidates for the desired isomorphism. Finally, by analyzing which groups are these (cataloged in the references [29,34]), we obtain the desired isomorphism. □

Then, these are cases in which it is possible to build a binary partitioning.

Definition 13.

A geometrically uniform partition $C/C^{\prime }$ is a partition of a geometrically uniform signal set C with a generator group $U\left(C\right)$, induced by a normal subgroup $U^{\prime }$ of $U\left(C\right)$. The elements of the partition $C/C^{\prime }$ are subsets of C that corresponding to cosets of $U^{\prime }$ in $U\left(C\right)$.

Theorem 8

([8]). Let $C/C^{\prime }$ be a geometrically uniform partition. Then, the subsets of C in the geometrically uniform partition are geometrically uniform, mutually congruent, and have $U^{\prime }$ as a generator group in common.

Theorem 8 may be extended when $U\left(C\right)/U\left(C^{\prime }\right)/U\left(C^{″}\right)/\dots$ is a chain of partitions for the groups, and in this case, there is a corresponding chain $C/C^{\prime }/C^{″}\dots$ of geometrically uniform partitions, where in each level the subsets are geometrically uniform, mutually congruent, and have the same generator group in common.

Proposition 2.

A partition $C/C^{\prime }$ has an isometric labeling by a group G if the following conditions are satisfied:

(1)

C is geometrically uniform;

(2)

its subsets are geometrically uniform and mutually congruent;

(3)

there is a group of isometries between $U\left(C\right)$ and $U\left(C^{\prime }\right)$ such that $U\left(C^{\prime }\right)$ is a generator group of C, $U\left(C^{\prime }\right)$ is a common generator group of subsets of C, normal in $U\left(C\right)$, and isomorphic to $U\left(C\right)/U\left(C^{\prime }\right)$.

Since we are considering $GU$ codes on compact surfaces, the labeling groups are always finite, and therefore, they are always in biunivocal correspondence with the respective signal sets. This situation allows chains of subgroups to be treated from the perspective of fair partitions, which were introduced in [38].

Usually, the chain is chosen to maximize the minimum squared distance between distinct points of a set partitioning at the same level, so that the distance grows as fast as possible at each level. In the following examples, the chains always begin by $G^{*}/G$. Therefore, we have the constellations corresponding to $G^{*}$ and G at zero and one level, respectively.

Example 1

(A non-binary partitioning). Let us consider the following chain of partitioning: $Z_2⋉(Z_2\times Z_6)/Z_2\times Z_6/Z_6/Z_2$ from case $(2,6,6)$. This chain may be viewed in Figure 4. It must be observed that it is also possible to use chain $Z_2⋉(Z_2\times Z_6)/Z_2\times Z_6/Z_6/Z_3$.

Example 2.

Now we preset the binary cases. Group $G^{*}=Z_2⋉Z_8$ from case $(2,8,8)$ allows the binary chain partitioning $G^{*}/G/Z_4/Z_2$ shown in Figure 5.

Example 3.

The partitioning chain $G^{*}/G/Z_4/Z_2$, shown in Figure 6, is enabled by the group $G^{*}$, which corresponds to $(4,4,4)$.

Example 4.

In the case $(2,4,8)$, one has $G^{*}=Z_2⋉D_{283}$ and $G=D_{283}$, which is the semi-dihedral group of order 16. Thus, $D_{283}$ has three order 8 subgroups: the cyclic $Z_8$, the quaternion $Q_2$, and the dihedral $D_4$. Consequently, at the third level of the chain, we may proceed in three different ways. In addition, there are other ramifications for the other levels, thereby enabling various possibilities to obtain alternative chains. For instance, chain $G^{*}/G/Z_8/Z_4/Z_2$ results in the labeling shown in Figure 7.

Remark 1.

The chain in Example 4 generates a partitioning in the form ${\left(Z_2\right)}^n$ with $n=5$, resulting in 32 cosets classes for the corresponding lattice. Note that this fact exposes a huge difference in the search for binary partitions between signal sets in hyperbolic and Euclidean spaces. Forney observed that lattices in the Euclidean plane may provide, at most, 16 coset classes in a partitioning chain. Generally, the n-dimensional Euclidean space admits a maximum of $4^n$ partitions for the label chain. Example 4 makes clear that this rule does not apply to partitions in hyperbolic spaces.

Theorem 9.

The greater the genus of compact surface, the more tiling and $OP$-tiling groups it has. In particular, for genus 2, we have more than 16 coset classes in a partitioning chain.

5. Conclusions and Discussion

This work presents two contributions: constellations of signals labeled by a group G are obtained, as well as Ungerboeck partitioning in the hyperbolic plane. Essentially, even though theoretical, it contributes to the modulation problem when proposing labelings. With Ungerboeck’s partitions, we are presenting a code coming from the hyperbolic plane, and much more. We show that in the hyperbolic plane, it is also possible to unify modulation and encoding in a single step. In particular, we build labelings for geometrically uniform codes on the double torus through tiling groups for all the 11 regular tessellations on the double torus that are derived from triangular Fuchsian groups. As an application, partitioning chains are constructed for geometrically uniform codes using soluble groups as labeling, which, in some cases, results in an Ungerboeck partitioning to the surface.