Algorithm for Generating All Optimal 16-QAM BI-STCM-ID Labelings

The BI-STCM-ID system yields a space-time diversity gain over BICM-ID: since the signals representing given parts of encoded data train are transmitted at least twice (each time through different antennas and in different time-slots), the signals are more resistant to detrimental effects of channel fading and additive noise [16, Sec. 3.3.3]. To boost the space-time diversity gain, \(N_{R}>1\) receive antennas can be applied.

Both BI-STCM-ID transmitter and receiver are shown in Fig. 1. At the transmitter, the data bit sequence \(\underline{{\mathbf {d}}}\) is encoded. Then, the length-\(M\) codeword \(\underline{{\mathbf {c}}}\) is bit-wise interleaved (by the block denoted by \(\pi \)) and the interleaved codeword \(\underline{{\mathbf {v}}}\) is divided into length-m horizontal binary vectors \({\mathbf {v}}_{1}\ldots {\mathbf {v}}_{\vartheta }\ldots {\mathbf {v}}_{\left\lceil M/m\right\rceil }\), where \(\vartheta \) is a given time instant. Each vector \({\mathbf {v}}_{\vartheta },\forall \vartheta \), is mapped onto a baseband complex signal \(s_{\vartheta }\in \chi \), according to the labeling map \(\omega \) (\(\chi \) is the signal constellation—16-QAM herein). Afterward, the space-time encoder takes q consecutive signals, \(s_{\tau },\ldots ,s_{\tau +q-1}\) to specify the tth \(L\times N_{T}\) space-time codeword \({\mathbf {X}}_{t}\), whose entries are the signals to be transmitted through \(N_{T}\) antennas within L timeslots. For convenience, an overall mapping rule, denoted by \({\mathcal {\varpi }}\), is introduced to directly associate length-\(K\left( =q2^{m}\right) \) vectors with the space-time codewords: \({\mathbf {X}}_{t}=\varpi \left( \left[ {\mathbf {v}}_{\tau }\,\,{\mathbf {v}}_{\tau +1}\,\,\ldots \,\,{\mathbf {v}}_{\tau +q-1}\right] \right) \). For the most popular, orthogonal design by Alamouti [17], \(q=L=N_{T}=2\), andwhere \(\left( \cdot \right) ^{*}\) means complex conjugate.

Similarly to BICM-ID, the receiver of BI-STCM-ID performs iterative decoding. In the case of orthogonal space-time codes [18, 19], the signals \(\tilde{y}_{\vartheta },\vartheta =\tau ,\ldots ,\tau +q+1\), which are connected with individual signals \(s_{\vartheta }\) by the following formula:are recovered from the received space-time symbol \({\mathbf {Y}}_{t}={\mathbf {X}}_{t}{\mathbf {H}}_{t}+{\mathbf {N}}_{t}\) by simple linear processing, which can be treated as a kind of space-time decoding. In the previous sentence, \({\mathbf {H}}_{t}\) is the current channel gain matrix, whose entries are i.i.d. random variables \(\sim {\mathcal {CN}}(0,1)\), and \({\mathbf {N}}_{t}\sim {\mathcal {CN}}(0,N_{0})\) contains the additive Gaussian noise samples characterized by the noise power spectral density \(N_{0}\). Next, \(\tilde{h}_{t}\) is the gain of an effective channel over which every \(s_{\vartheta },\vartheta =\tau ,\ldots ,\tau +q-1\), is transmitted, and \(\tilde{n}_{\vartheta }\) is an effective noise sample. Note that all the signals \(s_{\tau },\ldots ,s_{\tau +q-1}\), associated with the \(t\)th space-time codeword \({\mathbf {X}}_{t}\), must be affected by the same \(\tilde{h}_{t}\) to make the space-time decoding robust. The demapper design is the same as for conventional BICM-ID, i.e., at each time instant \(\vartheta \), the demapper outputs extrinsic log-likelihood ratios (LLRs) \({\mathbf {L}}_{\vartheta }^{[dem,E]}\) for all bits mapped onto the \(\vartheta \)th signal at the transmitter side. The sequences \({\mathbf {L}}_{\vartheta }^{[dem,E]}\) are concatenated to form \({\mathbf {\underline{L}}}^{[dem,E]}\), whose deinterleaved version, i.e. \({\mathbf {\underline{L}}}^{[enc,A]}=\pi ^{-1}({\mathbf {\underline{L}}}^{[dem,E]})\), feeds the SISO (soft-input soft-output) decoder. The extrinsic LLRs outputted by the decoder, \({\mathbf {\underline{L}}}^{[enc,E]}\), are interleaved again and serve the demapper during the next iteration as the a priori knowledge \({\mathbf {L}}_{\vartheta }^{[dem,A]}\). After several iterations, the LLRs \({\mathbf {\underline{L}}}^{[dec,E]}\), related to the data bits \({\mathbf {\underline{d}}}\), are computed by the decoder. Passed through a decision unit, they play the role of data estimates \(\hat{{\mathbf {\underline{d}}}}\). A detailed description of demapper and SISO decoder routine is provided, e.g., in [11] and [20], respectively.

To maximize the benefits derived from iterative processing, the system should reach the EF state. (In that case the mutual information between the encoded data bits \(\underline{{\mathbf {v}}}\) and respective LLRs, \({\mathbf {\underline{L}}}^{[enc,E]}\), is 1 bit.) The EF state has important theoretical implications, e.g., the position of a tight upper BER versus SNR bound (EF bound) can be provided [9]. Asymptotically, i.e., for \({\mathrm {SNR}}\rightarrow \infty \), the EF bound approaches a straight line on a logarithmic scale plot. A horizontal shift of that line is called the asymptotic coding gain and is denoted by \(\widetilde{\varOmega }^{2}\). It represents an impact of the overall space-time mapping rule \(\varpi \) on the system performance. The higher asymptotic coding gain, the better asymptotic system performance. Theorem 1 from [11] says that to maximize the asymptotic coding gain of the systems employing orthogonal space-time codes it is enough to search for a proper constellation labeling in order to maximize the \(\left( -p\right) \)th power mean of Euclidean distances between the signals whose labels differ in exactly one bit, sincewhere \(\tilde{s}_{k}\) is a constellation point with opposite bit in the kth position of its label in comparison with s.

As already mentioned, the author of the current paper has already shown [12] that vast majority of the optimal 16-QAM labelings found in [11] for BI-STCM-ID performing specific space-time diversity order p are equivalent to each other and, as such, they can be employed alternatively. Moreover, all of them have identical asymptotic coding gain (3) as the \(M16^{a}\) found presented in [6]. The original \(M16^{a}\) labeling is shown in Fig. 2 for the Reader’s convenience. Only for \(p=1\) (no space-time diversity gain—pure BICM-ID system) another labeling (named \(M16^{r}\) in [6]) appeared to be slightly (ca. 0.007 dB) better than \(M16^{a}\), asymptotically. Apart from this negligible performance loss, \(M16^{a}\) seems to be a labeling that is suitable for BI-STCM-ID in conjunction with any space-time block code of orthogonal design as well as for single-input single-output transmission.

Distance spectrum analysis [21] is a comprehensive method to study the construction of labeling maps. In the EF case, the distance spectrum is constituted by a set of squared Euclidean distances between constellation points s and \(\tilde{s}_{k}\), \(\forall s\in \chi , \, k=1,\ldots ,m\). In order to study labelings’ properties more thoroughly, it was proposed in [22] to analyze the spectrum point-by-point, i.e., to count the number of specific \(\left| s-\tilde{s}_{k}\right| ^{2},\, k=1,\ldots ,m\), entries for a given point \(s\in \chi \). Such a point-wise distance spectrum is defined asIt was shown in [22] that for \(M16^{a}\)-compliant labelings there are only 3 types (namely \(\alpha \), \(\beta \) and \(\gamma \)) of constellation points considering their spectra as presented in Fig. 2. Histograms of the point-wise distance spectra for the original \(M16^{a}\) labeling from [6], are listed in Table 1.

Note that d is the squared Euclidean distance between neighboring constellation points. Using the Pythagorean theorem, one can easily calculate the distances between given points of 16-QAM constellation, shown in Fig. 2, e.g., the squared distance from E to L is \((\sqrt{d})^{2}+(3\sqrt{d})^{2}=10d\).

Now we can formalize a definition of \(M16^{a}\)-compliant labeling for better clarity:

Taking into account the relation between point-wise distance spectra and the asymptotic coding gain (3) [the elements of all point-wise distance spectra appear in (3)], it is obvious, that two labelings with the same spectral properties yield identical asymptotic coding gain.

Exploiting labeling diversity consists of using different labeling maps, i.e., \(\omega ^{\left( 1\right) }\) and \(\omega ^{\left( 2\right) }\), within adjacent transmit streams, as shown in Fig. 3. Note that vectors \({\mathbf {v}}_{2t}\) and \({\mathbf {v}}_{2t+1}\) are not demultiplexed. Instead, they feed both mappers simultaneously. The block denoted by \(\varPi \) is to alter even and odd signals, i.e., \(s_{2t}^{\left( 2\right) }\) and \(s_{2t+1}^{\left( 2\right) }\). Thus, the resultant space-time codeword readsThanks to the signal exchange within the lower transmit stream, each of the signals \(s_{\vartheta }^{\left( 1\right) }\) and \(s_{\vartheta }^{\left( 2\right) },\forall \vartheta \), carrying the same part \({\mathbf {v}}_{\vartheta }\) of the codeword \(\underline{{\mathbf {v}}}\), reaches the receiver in a different timeslot than the other. Such a trick, inherited from space-time codes, alleviates the detrimental effect of additive Gaussian noise on the signal demodulation. At the same time, LD scheme fights against fading, since \({\mathbf {v}}_{\vartheta },\forall \vartheta \) is transmitted twice, each time through different channels.

At the beginning of the research on labeling diversity, the optimal \((\omega ^{\left( 1\right) },\omega ^{\left( 2\right) })\) pair, i.e., the one maximizing the asymptotic coding gain, was searched for by means of Binary Switching Algorithm (BSA) [14] with the assumption that \(\omega ^{(1)}\) is one of the \(M16^a\)-compliant labelings. Later, it was noticed that both labelings that constitute the optimal pair are \(M16^{a}\)-compliant [15].

A receiver deriving its good performance from labeling diversity is similar to that of BI-STCM-ID, but the received space-time codeword cannot be decoded prior to demodulation, and thereby, the computational payload grows as for a multidimensional mapping technique from [23].

When applied to a \(p=4\; 2 \times 2\) MIMO system, LD scheme yields \(\widetilde{\varOmega }^{2}=2.8752\) in comparison with 2.3414 for respective BI-STCM-ID. In other words, there is the labeling diversity gain of \(10\log _{10}\tfrac{2.8752}{2.3414}=0.89\,{\mathrm {dB}}\). The asymptotic coding gain for BI-STCM-ID is computed according to (3). The interested reader is referred to [14] to get known how to obtain \(\widetilde{\varOmega }^{2}\) for LD scheme and to see that LD scheme exhibits full diversity order, i.e., it meets a full-rank criterion, concerned in [18, Sec. II-B].

This section is, mainly, to show that every \(M16^a\)-compliant labeling that bears the features of \(M16^{a}\) must follow a 2–3–2–3 rule defined as follows:

We will consider all values the Hamming distance between the labels of two given neighboring corner constellation points ¹ can take and examine if it is possible to obtain a valid \(M16^{a}\)-compliant labeling by referring to the spectral properties highlighted in the previous section. Let us recall that the point-wise distance spectrum entries are the distances between constellation points, associated with the labels differing exactly in one bit from each other.

From now on a permutation function \(\psi \left( \cdot \right) \) of binary numbers \(b_{1}\ldots \, b_{4}\) and their negations \(\overline{b_{1}}\ldots \,\overline{b_{4}}\) will be used to abstract the proofs from any concrete labeling map. That function returns a vector of binary numbers. Individual constellation points will be referred to by the letters shown in Fig. 2. The box-plus operator, e.g., \({\mathbf {a}}\boxplus {\mathbf {b}}\), will represent the Hamming distance between respective vectors, and \({\mathcal {V}}_{XY\ldots }\) will denote a set of labels that can be assigned to any of the points indicated in the subscript (X, Y, etc.).

The same reasoning can be applied to any pair of consecutive corner constellation points since every corner point exhibits identical distance spectrum. In the light of both Theorems 1 and 2 any \(M16^{a}\)-compliant labeling ensures that the labels of adjacent corner points differ from each other in either 2 or 3 bits. The following theorems are to show that in both cases the 2–3–2–3 rule holds.

The theorem holds for any pair of adjacent corner constellation points, but it is not enough to state that every \(M16^{a}\)-compliant labeling holds the 2–3–2–3 rule. To prove such a hypothesis, one more case (in which the labels of arbitrarily chosen adjacent corner constellation points differ in 3 bits) must be considered.

We have considered all possible values the Hamming distance between adjacent corner 16-QAM constellation points can take. Now we are allowed to introduce the following corollary.

Note that the above corollary is not constructive, i.e., it does not explain how to design the \(M16^{a}\)-compliant labelings. Nevertheless, it allows us to start labeling design from assigning proper labels to the corner points.

We should consider two kinds of \(M16^{a}\)-compliant labelings: “vertically” and “horizontally” oriented.

Additionally, labelings of both kinds can be reflected. To avoid confusion over numerous labeling configurations, from now on we will consider only the vertically oriented labelings. For horizontally oriented labelings, it is enough to rename the constellation points to keep consistency. Such approach is fully justified, since neither rotation nor reflection of any 16-QAM labeling affects its performance.

In general, the \(M16^{a}\) point-wise distance spectra (shown in Table 1) do not indicate which of the constellation points constitute the \(\left( s,\tilde{s}_{k}\right) \) pairs for given \(k\). Nevertheless, some pairs are unambiguous due to the constellation’s (not: labeling’s) properties, i.e., there is only one constellation point a given Euclidean distance far from the considered point. The situation is illustrated in Fig. 4 (resolved connections are shown by solid lines). Making use of the constellation properties, one can easily conclude that:Some other potential ambiguities can be resolved by realizing that a given distance must appear simultaneously in spectra of two points. From that remark it can be concluded thatThe only uncertainty concerns some \(5d\) entries. That problem is partially solved while making the proof of Theorem 3, i.e., according to (28), the labels of points \(J\) and \(K\) differ in exactly one bit from both \({\mathbf {v}}_{A}\) and \({\mathbf {v}}_{D}\). As a result, the following theorem, claiming that any \(16^{a}\)-compliant labeling is almost fully defined by the corner points’ labels, can be issued.

According to the above theorem, an \(M16^{a}\)-compliant labeling can be obtained by fixing proper labels of the corner points and then by trying to associate labels to remaining points. It must be kept in mind that any valid solution must not violate the rules provided by the \(M16^{a}\) point-wise spectrum shown in Table 1.

Within this paragraph the following notation is used: \({\mathcal {V}}\) is a set consisting of all possible 4-bit binary vectors. Sets \({\mathcal {A}},{\mathcal {B}}\) and \({\mathcal {G}}\) contain only such labels that (at the current stage) are not forbidden for points of type \(\alpha ,\,\beta ,\,\gamma \), respectively, whereas \({\mathcal {W}}_{\rightharpoonup XY\ldots },{\mathcal {W}}\in \left\{ {\mathcal {A}},{\mathcal {B}},{\mathcal {G}}\right\} \) additionally limits the entries of \({\mathcal {W}}\) to such ones that differ exactly in one bit from every of the labels assigned previously to points listed in the subscript (X, Y, etc.). Finally, \(rand\left( \cdot \right) \) function returns a random element of its arguments. The algorithm explained below allows to obtain one of the \(M16^{a}\)-compliant labelings. It can be relaunched several times if one aims to get a variety of \(M16^a\)-compliant labelings. Consecutive algorithm steps are as follows:

Step 1. Assign the labels to the corner constellation points. For this end, define matrices ² Circulate the rows of \({\mathbf {W}}_{n}\) and \({\mathbf {W}}_{g}\), separately, downwards or upwards, random number of times to get \({\mathbf {W}}'_{n}\) and \({\mathbf {W}}'_{g}\), respectively. Then define \({\mathbf {W}}'\) as a vertical concatenation of \({\mathbf {W}}'_{n}\) and \({\mathbf {W}}'_{g}\), and permute the columns of \({\mathbf {W}}'\) to obtain \({\mathbf {W}}\). Finally, read length-4 binary labels from \({\mathbf {W}}\) row-by-row and associate them with consecutive corner constellation points \(A,D,M\), and \(P\), respectively. The method presented above guarantees that labels of the corner points hold the 2–3–2–3 rule. (Each row of \({\mathbf {W}}_{n}\) differs from the subsequent one ³ by 1, 2, 1, 2 bits, respectively, whereas the rows of \({\mathbf {W}}_{g}\)—holding the Gray rule—always differ in 1 bit from both the previous and the next one.) Finally, create a set consisting of all corner points’ labels:

Step 2. If the obtained corner points belong to a “horizontally” oriented labeling (cf. Definition 4), rename the constellation points as follows: A by M, B by I, C by E, D by A, E by N, F by J, G by F, H by B, I by O, J by K, K by G, L by C, M by P, N by L, O by H, and P by D. Thanks to that move there is no necessity to consider two labeling orientations within the next steps.

Step 3. Define disjoint subsets consisting of labels that can be associated with proper \(\gamma \) points, i.e., they must differ in exactly one bit from the labels of both \(A\), \(D\) and from the labels of both \(M\), \(P\), respectively (cf. the Proof of Theorem 5):

Step 4. Create four subsets \({\mathcal {B}}_{\rightharpoonup \ell }\), containing the labels differing in exactly one bit from the labels assigned previously to points \(A,\, D,\, M,\, P\), respectively:The labels from \({\mathcal {B}}_{\rightharpoonup \ell }\) will be assigned within next steps to proper \(\beta \) points.

Step 5. As the squared Euclidean distance between points \(E\) and \(I\) is \(d\) (i.e. the shortest possible one), it is obvious that such points should not be associated with the labels differing in one bit according to the \(M16^{a}\) spectrum. To avoid such a collision, assignandSince each label must be assigned to exactly one constellation point, \(B\) and \(N\) must be associated with the labels remaining in sets \({\mathcal {B}}_{\rightharpoonup D}\) and \({\mathcal {B}}_{\rightharpoonup P}\), respectively, after removal of \({\mathbf {v}}_{E}\) and \({\mathbf {v}}_{I}\), i.e.

Step 6. Now assign proper labels to points \(H\) and \(L\). They must differ from the labels associated with \(E\) and \(I\), respectively, in exactly one bit (the spectrum entries of \(10d\) are the distances between two \(\beta \) points, symmetrical with respect to the origin of the coordinate system). To satisfy such requirement, takeandConsequently,and

Step 7. The last task is to assign the labels to \(\gamma \) points. They must not differ in one bit from the labels belonging to any of four the nearest \(\beta \) points or to the rest of \(\gamma \) points. Otherwise, \(d\) or \(2d\) distances would occur in the spectrum. At this point only one collision has left for each \(\gamma \) point (with the label of respective second nearest \(\beta \) point). To hold the features of \(M16^{a}\), assign and

The algorithm starts with assigning the labels to corner points (Step 1). We proceed according to the method shown in Sect. 4.1. Let us assume that \({\mathbf {W}}_{n}\) is circulated 2 times downwards and \({\mathbf {W}}_{g}\)—three times. A resultant concatenated matrix isNow let us assume that the permutation function exchanges the 1st column with the 2nd column, and the 3rd column with the 4th one to produce the final matrixWe read consecutive rows of \({\mathbf {W}}\) to get \({\mathbf {v}}_{A}=\left[ 0101\right] ,\,{\mathbf {v}}_{D}=\left[ 1100\right] ,\,{\mathbf {v}}_{M}=\left[ 0010\right] ,\,{\mathbf {v}}_{P}=\left[ 1011\right] \), as shown in Fig. 5a. The obtained labeling is “vertically” oriented, hence Step 2 is skipped. In Step 3, we define the labels that can be assigned to points J and K. They have to differ in exactly one bit from the labels of both points A and D, i.e., they belong to the set \({\mathcal {V}}{}_{JK}={\mathcal {G}}_{\rightharpoonup \! AD}=\left\{ \left[ 0100\right] ,\left[ 1101\right] \right\} \) (Fig. 5b). Similarly, we assign the labels that are allowed for points F and G: \({\mathcal {V}}{}_{FG}={\mathcal {G}}_{\rightharpoonup \! MP}=\left\{ \left[ 0011\right] ,\left[ 1010\right] \right\} \) (Fig. 5c). At this stage we getand dispatch its entries to the subsets of labels that can be assigned to consecutive \(\beta \) points (Step 4). For example, the labels of points \(B\) and \(E\) must both differ exactly in one bit from the label of \(P\) (there is no other way to meet requirement for double \(13d\) entry in the spectrum of point \(P\)). Thus, we assign \({\mathcal {V}}{}_{BE}\!\!=\!\!{\mathcal {B}}_{\rightharpoonup P}\!\!=\!\!\left\{ \left[ 0000\right] ,\left[ 0110\right] \right\} \), and—by analogy—\({\mathcal {V}}{}_{IN}\!\!=\!\!{\mathcal {B}}_{\rightharpoonup D}\!\!=\!\!\left\{ \left[ 1000\right] ,\left[ 1110\right] \right\} \) (Fig. 5d), \({\mathcal {V}}{}_{LO}\!\!=\!\!{\mathcal {B}}_{\rightharpoonup A}\!\!=\!\!\left\{ \left[ 0001\right] ,\left[ 0111\right] \right\} \), \({\mathcal {V}}{}_{CH}\!\!=\!\!{\mathcal {B}}_{\rightharpoonup M}\!\!=\!\!\left\{ \left[ 1001\right] ,\left[ 1111\right] \right\} \) (Fig. 5e). Since further steps are fully determined, at this stage (Step 5) we finally decide about the labeling rule, i.e., we can assign \(\left[ 0000\right] \) to point \(E\) and \(\left[ 1110\right] \) to point \(I\) or \(\left[ 0110\right] \) to point \(E\) and, consequently, \(\left[ 1000\right] \) to \(I\). Note that in every case \({\mathbf {v}}_{E}\boxplus {\mathbf {v}}_{I}>1\) holds. Let us choose the second option, i.e., \({\mathbf {v}}_{E}=\left[ 0110\right] \), \({\mathbf {v}}_{I}=\left[ 1000\right] \) (Fig. 5f). In consequence, the only label from \({\mathcal {B}}_{\rightharpoonup P}\) that can be assigned to \(B\) is \(\left[ 0000\right] \) and, by analogy, we must associate \(N\) with \(\left[ 1110\right] \) (Fig. 5g). In Step 6, to keep \(10d\) distances in spectra of points \(E,H,I,L\), we must take \({\mathbf {v}}_{H}=\left[ 1001\right] ,{\mathbf {v}}_{L}=\left[ 0111\right] \), and—to preserve labeling’s unambiguity—\({\mathbf {v}}_{C}=\left[ 1111\right] ,{\mathbf {v}}_{O}=\left[ 0001\right] \) (Fig. 5h). The labels associated with \(\gamma \) points are determined by the assignments made previously for \(\beta \) points. Thus, in Step 7 we get \({\mathbf {v}}_{F}=\left[ 0011\right] \), \({\mathbf {v}}_{G}=\left[ 1010\right] \), \({\mathbf {v}}_{J}=\left[ 1101\right] \), and \({\mathbf {v}}_{K}=\left[ 0100\right] \).

The presented algorithm generates different \(M16^{a}\)-compliant labelings, however, some of them are rotated or flipped version of the others.

Let us start the analysis from assigning labels to the corner points. According to Corollary 1, they must conform the 2–3–2–3 rule. When executing Step 1 of the algorithm delivered in Sect. 4.1, we can choose the positions of binary labels to be Gray-labeled (g-positions) in \(Q_{p}=\left( {\begin{array}{c}4\\ 2\end{array}}\right) \) ways. The remaining positions are, automatically, naturally-labeled (n-positions). Within each group we can choose one of four constellation points from which we start assigning labels’ parts on n- and g-positions, respectively \(\left( Q_{s}=\left( {\begin{array}{c}4\\ 1\end{array}}\right) \right) \), and we can proceed clock- or counterclockwise \(\left( Q_{d}=\left( {\begin{array}{c}2\\ 1\end{array}}\right) \right) \) when assigning subsequent labels’ parts. In consequence, the total number of possible assignments of 4-bit labels holding the 2–3–2–3 rule to the corner constellation points counts \(Q'=Q_{p}\left( Q_{s}Q_{d}\right) ^{2}=384\). The product \(Q_{s}Q_{d}\) is squared as g- and n-positions are considered separately. Having assigned the labels to the corner points, there is still one degree of freedom, as Theorem 5 states. Thus, the total number of \(16^{a}\)-compliant labels is \(Q=2Q'=768\).

The algorithm input is an \(M16^{a}\)-compliant labeling. The algorithm steps are as follows:

Step 1. (define a “raw” complementary labeling compliant with Corollary 2) Take the labels of corner constellation points of the reference labeling, negate all their bits and assign them to the same points as their origins in the reference labeling.

Step 3. (optional; get alternative labels of corner constellation points) Execute one of the following operations:Having generated the labels of the corner constellation points, one can easily get a complete complementary labeling map by using the algorithm delivered in Sect. 4. There are 8 different ways to specify the corner constellation points of the complementary labeling: in Step 3, one of 7 optional operations can be executed or the step can be skipped. Note that for each assignment of the labels to the corner constellation points there is one degree of freedom as Theorem 5 says. Accordingly, 16 complementary labelings can be found from one reference labeling.

As an example, the reference labeling, delivered in Sect. 4.2 and resultant complementary ones are presented in Table 2; \(\alpha \) points and \(\gamma \) points are written in bold and in italic, respectively. Interestingly, any label associated with \(\alpha \) point according to the reference labeling is assigned to one of \(\gamma \) points under each of the complementary labeling rules. The same observation was made in [15] for a few \(M16^{a}\)-compliant pairs, found by BSA.

For reader’s convenience, consecutive steps of the algorithm are presented in Fig. 6. More precisely, Fig. 6a presents the reference labeling developed in Sect. 4.2. The “raw” complementary labels of the corner points, i.e., the result of the algorithm’s Step 2, are shown in Fig. 6b. The result of disturbing the order of “raw” labels (Step 3) is shown in Fig. 6c. Finally, Fig. 6d presents the final complementary labeling, which is the first complementary labeling with no optional operation from Table 2.