Subspace Coding for Networks with Different Level Messages

Abstract

We study the asymptotically-achievable rate region of subspace codes for wireless network coding, where receivers have different link capacities due to the access ways or the faults of the intermediate links in the network. Firstly, an outer bound of the achievable rate region in a two-receiver network is derived from a combinatorial method. Subsequently, the achievability of the outer bound is proven by code construction, which is based on superposition coding. We show that the outer bound can be achieved asymptotically by using the code presented by Koetter and Kschischang, and the outer bound can be exactly attained in some points by using a q-analog Steiner structure. Finally, the asymptotically-achievable rate region is extended to the general case when the network has m receivers with different levels.

1. Introduction

Network coding, introduced in [1,2], has attracted a substantial amount of research attention. It is a technique in which the intermediate node is allowed to make a combination of its received packets before sending the combined packet out to the network. This method can effectively improve the network throughput. However, there are still many problems to be studied, such as the collection of information about the network topology [3]. As the scale of the network grows, the complexity of network code construction increases accordingly. To address this issue, random network coding was proposed by Ho et al. [4] without considering network topology, where the intermediate nodes select coding coefficients at random from a finite field. It becomes an effective and robust tool when the network topology changes dynamically, especially in the case of a wireless network. Furthermore, since the characteristics of the wireless channel are time-varying in general, packets lost and errors are important factors affecting transmission performance. Therefore, error control in wireless network coding is essential [5,6].

Taking the advantage of the distance property of vector space, Koetter and Kschischang proposed the subspace metric codes for random network coding [7], where a subspace is used to represent a codeword. Even if partial changes occur in the received subspace, as long as the distance between the received subspace and the transmitted subspace satisfies a certain distance relationship, the message could still be decoded successfully. Closely relevant works about the coding bounds and the packing and covering properties of subspace codes are presented in [8,9,10]. However, the existing works about subspace codes are based on the multicast network model.

In this paper, we study a real-time media distribution system based on heterogeneous wireless networks, where end users are intelligent devices, such as smart TVs, mobile phones and computers. These terminals access the networks with different link capacities. There are several factors that make the link capacities different, such as the various ways that they access the networks (e.g., WLAN or mobile network), the packets lost and errors (due to the fault of the intermediate nodes or link failure) [11,12]. In this case, the terminals with high link capacity can receive more useful data, which means that some receivers are “stronger” than the others. For example, because they access the networks in a more stable way, they can always receive more than the “weaker” ones. Each end user wants to maximize the utilization of his link capacity to provide his best service. To meet the diverse requirements of the users, it is complex and a waste of resources to design the transmission approach for each user. A better solution is coding at the source node; then, the source node broadcasts the same encoded packets to the receivers, and each user collects as many packets as possible and then decodes to meet his requirement. A trivial coding method is to design a code corresponding to the “weaker” receiver. However, in this way, the “stronger” node cannot get his best service.

We assume that the media can be divided into several different priority levels according to their importance. The higher priority can ensure the basic demand of users. Meanwhile, the lower priority can guarantee the additional needs of users. To simplify the problem, we take the simplest case that there are only two receivers in the network. First, we derive an outer bound for the asymptotically-achievable rate region by a combinatorial method. Then, we prove the achievability of the outer bound by code construction with the codes that were proposed by Koetter and Kschischang (K-K codes) [7]. However, K-K codes require the dimension of ground space to be sufficiently large. We observe that the q-analog Steiner structure can be used in our construction. Our outer bound could be exactly attained in some points using a q-analog Steiner structure. We further extend our result to the general case of m receivers with different link capacities.

The rest of this paper is organized as follows. In Section 2.1, we briefly review the subspace code. Then, we observe that deletion correcting is equivalent to deletion and insertion error correcting in constant dimension codes. In Section 2.2, we extend the model to broadcast, which leads us to the definition of broadcast error correction network codes (BECNC). We state the asymptotically-achievable rate region of BECNC in Section 3. The main results are proven in Section 4. In Section 5, we present that the outer bound can be exactly attained in some points using the q-analog Steiner structure. In Section 6, we generalize the rate region to the network with more than two receivers.

2. Preliminaries and Our Model

2.1. Previous Results: Subspace Metric Codes

We begin with previous results about subspace metric codes, which were proposed by Koetter and Kschischang [7]. It is necessary to introduce the previous results of subspace metric codes, since our works are based on them.

In the “noncoherent” model, the transmitter and receiver are assumed to have no knowledge of the channel transfer matrix. Let ${\mathbb{F}}_q$ be a finite field with q elements. We use ${\mathbb{F}}_q^{l\times k}$ to denote the set of all $l\times k$ matrices over ${\mathbb{F}}_q$. In the error free case, the transmission model can be characterized as $\mathbf{Y}=\mathbf{F}\mathbf{X}$, where $\mathbf{F}\in {\mathbb{F}}_q^{l\times k}$ is a full rank random matrix (the channel transfer matrix), $\mathbf{X}\in {\mathbb{F}}_q^{k\times n}$ is the transmitted matrix whose rows can be considered as source packets [11] and $\mathbf{Y}\in {\mathbb{F}}_q^{l\times n}$ is the received matrix whose rows can be considered as received packets.

Since the receiver does not know $\mathbf{F}$, he only knows that the rows of $\mathbf{X}$ and $\mathbf{Y}$ span the same subspace. Then, he can correctly recover the transmitted space when no error occurs, if we regard space spanned by the rows of $\mathbf{X}$ as a codeword.

However, the transmitted space will be a subspace of the received space by the receiver when an insertion error occurs, whereas the receiver will receive a subspace of the transmitted space when a deletion occurs [7].

${\mathbb{F}}_q^n$ can be regarded as an n-dimensional vector space over ${\mathbb{F}}_q$. Let ${\mathcal{P}}_q\left(n\right)$ denote the set of all subspaces of ${\mathbb{F}}_q^n$, forming the n-order projective space over ${\mathbb{F}}_q$ [17]. A subspace metric code $\mathcal{C}$ is a nonempty set of subspaces of ${\mathbb{F}}_q^n$, where each codeword is a vector space spanned by the rows of a message matrix. Let $U,V\in {\mathcal{P}}_q\left(n\right)$ be two subspaces; the subspace distance between them is defined as $d(U,V)=dim\left(U\right)+dim\left(V\right)-2dim(U\cap V)$, where $dim\left(U\right)$ is the dimension of U. The minimum distance of code $\mathcal{C}$ is defined as $D\left(\mathcal{C}\right)={min}_{U,V\in \mathcal{C}:U\ne V}d(U,V)$. If:

$$D\left(\mathcal{C}\right)>2(t+\rho ),$$

(1)

then a minimum distance decoder will produce the transmitted space from the received space, where t and ρ denote the maximum number of deletion and insertion errors induced by the channel, respectively. Deletion is actually the packets lost, and insertion error is equivalent to malicious attack.

In this paper, we only consider the constant dimension codes, where the dimensions of all codewords in $\mathcal{C}$ are the same. Let ${\mathcal{P}}_q(n,k)$ denote the set of all k-dimensional subspaces $(k\le n)$ of the n-dimensional vector space ${\mathbb{F}}_q^n$. This means that constant dimension code $\mathcal{C}$ is a subset of ${\mathcal{P}}_q(n,k)$. The normalized weight is defined as $\lambda =k/n$, where k is the dimension of codewords. The rate of the code is defined as $R=\frac{{log}_q\left|\mathcal{C}\right|}{nk}$.

In [7], Koetter and Kschischang obtained the Singleton-type bound of the subspace codes and constructed a Singleton bound-achieving code using the linearized polynomial. We refer to this code as the K-K code in the following. The Singleton-type bound is shown in the following lemma.

Lemma 1 (Corollary 10 of [7]). Let $\mathcal{C}$ be a collection of subspaces in ${\mathcal{P}}_q(n,k)$, with normalized minimum distance $\delta =\frac{D\left(\mathcal{C}\right)}{2k}$. The rate of $\mathcal{C}$ is bounded by:

$$R\le (1-\delta )(1-\lambda )+o\left(1\right),$$

(2)

where $\lambda =k/n$ is the normalized weight and $o\left(1\right)$ approaches zero as n grows.

They also mentioned that, for the decoder, the effects of insertion and deletion are equivalent in constant dimension codes. Furthermore, there may be an intersection between the insertion subspace and the transmitted subspace, which would possibly decrease the number of deletions seen by the receiver. In other words, the negative impact brought by simple deletion is not less than the negative impact caused by deletion and insertion simultaneously. Next, we will discuss the case of only deletions.

Observe that a subspace $V_r$ is received at the receiver; the minimum distance decoder will decode $V_r$ to $V_s$, if the distance between $V_r$ and $V_s$ is minimal among all of the codewords in $\mathcal{C}$, i.e.,

$$d(V_r,V_s)=\underset{V\in \mathcal{C}}{min}d(V_r,V).$$

(3)

We define the operation of deletions as mapping ${\mathcal{D}}_{\tau }$. For a given k-dimensional subspace V, ${\mathcal{D}}_{\tau }\left(V\right)$ produces a random $(k-\tau )$-dimensional subspace of V, where $\tau \ge 0$. We say that a code is capable of correcting τ deletions, if it can correct τ deletions using the decoding criterion in (3). We refer to such a code as a τ-deletion-correcting code, and its minimum distance must satisfy:

$$D\left(\mathcal{C}\right)>2\tau .$$

(4)

Let $V_r={\mathcal{D}}_{\tau }\left(V\right)$ be the received subspace and $V^{\prime }\ne V$ be any other codeword in $\mathcal{C}$, then $D\left(\mathcal{C}\right)\le d(V^{\prime },V)\le d(V^{\prime },V_r)+d(V_r,V)$; it follows that $d(V^{\prime },V_r)\ge D\left(\mathcal{C}\right)-d(V_r,V)$. If the condition (4) could be satisfied, then $d(V^{\prime },V_r)>d(V_r,V)$, the minimum distance decoder will produce the transmitted subspace V from the received subspace.

Remark 1. Since Condition (4) coincides with Condition (1), a τ-deletion-correcting code can correct t deletions and ρ insertions, if $t+\rho =\tau$. Thus, it is sufficient for us to focus on deletion-correcting codes, because for this reason, all our results below for deletion hold for deletion and insertion, as well.

An $(n,k,M,\tau )$-deletion-correcting code $\mathcal{C}$ over ${\mathbb{F}}_q$ is a k-dimensional subspace code over ${\mathbb{F}}_q^n$ with M codewords whose maximum deletion-correcting capability is τ. The rate of code $\mathcal{C}$ is $R=\frac{{log}_{q}M}{nk}$.

Definition 1. A rate R is said to be $(\lambda ,\mu )$-asymptotically achievable if, for all $ϵ>0$ and sufficiently large n, there exists an $(n,k,M,\tau )$-deletion-correcting code, such that $\frac{{log}_{q}M}{nk}>R-ϵ$, where $\mu =\tau /k$ and $\lambda =k/n$.

The network model of [7] is multicast, which is actually a point-to-point communication channel with just one sender and one receiver. In next subsection, we will extend the model to broadcast, which consists of one sender and m receivers.

2.2. Network Model

We are motivated by a real-time media distribution system based on heterogeneous wireless networks, where end users are individual intelligent terminals, such as tablets, smart phones and computers. These intelligent terminals access the network with heterogeneous link capacities. The difference of link capacities may be caused by different access ways (e.g., WLAN and mobile network) or the instability of their links.

We assume that the media can be divided into different priority levels corresponding to the link capacity of receivers. The higher priority level guarantees the basic media quality, and the lower priority level corresponds to detailed information about media. Let $\{{\mathcal{M}}_1,{\mathcal{M}}_2,\cdots ,{\mathcal{M}}_m\}$ be a collection of m message sets with ordered priority, where the index $i\in \{1,\cdots ,m\}$ indicates the priority level, and the smaller index corresponds to the higher-priority level. Without loss of generality, we assume there are m receivers in the network, each of which has a different level of link capacity. Let $\{t_1,t_2,\cdots ,t_m\}$ be the ordered set of receivers, where the index $i\in \{1,\cdots ,m\}$ indicates the link capacity; the smaller index corresponds to the higher link capacity.

The media is encoded into packets that can be sent to the network. For arbitrary $l\in \{1,\cdots ,m\}$, the receiver $t_l$ downloads the packets with its link capacity constraint. Although there exist some packets lost and errors in its link, $t_l$ can recover the messages with priority levels $\{1,2,\cdots ,m-l+1\}$. Therefore, with respect to the receiver with lower link capacity, the receiver with higher link capacity can obtain more detailed information, and it can get clearer vision effects by decoding its received packets.

For simplicity of presentation, we focus the discussion on the network with two receivers nodes $t_1,t_2$. The extension to an arbitrary number of receivers is straightforward. This model can be regarded as a combinatorial version of the asymmetric two-output broadcast channel [18] in projective space. We show it in Figure 1. The media is divided into two priority level message sets ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$. The receiver $t_1$ has a higher link capacity than $t_2$. This means that the receiver $t_1$ can recover both messages $i\in {\mathcal{M}}_1$ and $j\in {\mathcal{M}}_2$; meanwhile, the receiver $t_2$ can only decode the message $i\in {\mathcal{M}}_1$ during the transmission. We assume that a message pair $(i,j)$ is encoded into a codeword with k packets. Let ${\tau }_1$ and ${\tau }_2$ be the numbers of errors occurring at the link of receiver $t_1$ and $t_2$, respectively. Receiver $t_1$ and $t_2$ can collect $(k-{\tau }_1)$ and $(k-{\tau }_2)$ independent packets with no error, respectively. We assume that ${\tau }_2>{\tau }_1$, i.e., the receiver $t_1$ can receive more correct packets than $t_2$.

Figure 1. Asymmetric two-output broadcast channel.

Figure 1. Asymmetric two-output broadcast channel.

Our aim is to design a code $\mathcal{C}$ with which the receivers can decode their messages correctly as long as they received $(k-{\tau }_1)$ and $(k-{\tau }_2)$ independent packets with no error, respectively. Meanwhile, we are interested in the achievable rate region of the code. Although both deletion and insertion errors should be considered, it is sufficient to consider deletion error according to Remark 1.

Let ${\mathcal{M}}_1=\{1,2,\cdots ,M_1\}$ and ${\mathcal{M}}_2=\{1,2,\cdots ,M_2\}$ be two message sets, where ${\mathcal{M}}_1$ has higher level priority. The message pair $(i,j)\in ({\mathcal{M}}_1,{\mathcal{M}}_2)$ is encoded into codeword $V_{i,j}$ of $\mathcal{C}$ by encoding mapping. Then, the codeword will be transmitted to the network. Due to the packets lost, the receiver $t_1$ can receive a $(k-{\tau }_1)$-dimensional subspace $U_1$, and the receiver $t_2$ can receive a $(k-{\tau }_2)$-dimensional subspace $U_2$. If the codewords satisfy some conditions, the messages $(i,j)$ and i can be decoded correctly at $t_1$ and $t_2$, respectively. The conditions will be discussed at the end of Section 4.1. In this case, the receiver $t_1$ can recover messages i and j. Meanwhile, the receiver $t_2$ can only recover message i. Next, we formally state the definition of such code.

Definition 2. Let $t_1$ and $t_2$ be the two receiver nodes of an acyclic single source network; the corresponding numbers of errors occurring at the link of receiver $t_1$ and $t_2$ are ${\tau }_1$ and ${\tau }_2$, respectively, ${\tau }_2>{\tau }_1$. A constant dimension code $\mathcal{C}\subseteq {\mathcal{P}}_q(n,k)$ is called an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC (broadcast error-correcting network code), if it satisfies that the two receivers can correct errors of ${\tau }_1$ and ${\tau }_2$, respectively. The cardinalities of the two corresponding message sets are $M_1$ and $M_2$.

We are interested in the maximum number of message set pairs $(M_1,M_2)$, when the dimension and the maximum numbers of correctable errors are given. Sometimes, the asymptotic rate pairs are also interesting.

The asymptotic rate pair is defined as $(R_1,R_2)$, where $R_i=\frac{{log}_q{M}_i}{nk},i=1,2$.

Definition 3. A rate pair of non-negative real numbers $(R_1,R_2)$ is said to be $(\lambda ,{\mu }_1,{\mu }_2)$-asymptotically achievable if, for all $ϵ>0$ and sufficiently large n, there exists an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC, such that $\frac{{log}_q{M}_i}{nk}>R_i-ϵ,i=1,2$, where ${\tau }_1/k={\mu }_1,{\tau }_2/k={\mu }_2$ and $k/n=\lambda$. The asymptotically-achievable rate region is the set of all asymptotically-achievable rate pairs.

3. Main Results

We now state the asymptotically-achievable rate region of the broadcast error-correcting network codes. The proof of the theorem will be presented in next section.

Theorem 1. The asymptotically-achievable rate region of an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC with corresponding error-correcting capability ${\tau }_1$ and ${\tau }_2$ over field ${\mathbb{F}}_q$ consists of pairs $(R_1,R_2)$ of non-negative numbers that satisfy the inequalities,

$$\begin{array}{ccc}& R_1& \ge 0,R_2\ge 0\hfill \end{array}$$

(5)

$$\begin{array}{ccc}& R_1& \le \left(1-{\mu }_1\right)\left({\lambda }_x-\lambda \right),\hfill \end{array}$$

(6)

$$\begin{array}{ccc}& R_2& \le \left(1-{\mu }_2\right)\left(1-{\lambda }_x\right),\hfill \end{array}$$

(7)

where x is an auxiliary variable, such that $k\le x\le n$. The normalized weights are ${\lambda }_x=x/n,\lambda =k/n$, and the normalized error-correcting capabilities are ${\mu }_1={\tau }_1/k,{\mu }_2={\tau }_2/k$.

4. Proofs

Before proving the theorem, we introduce some auxiliary results in combinatorial mathematics, which are used in the proof of our results.

4.1. Combinatorial Lemmas

This part, however, is rather technical. The readers who are not interested in it can just skim the conclusion without missing the essence of this section.

The number of elements in ${\mathcal{P}}_q(n,k)$ is given by the Gaussian coefficient,

$$\left|{\mathcal{P}}_q(n,k)\right|={\left[\begin{array}{c}n\\ k\end{array}\right]}_q=\frac{(q^n-1)(q^{n-1}-1)\cdots (q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\cdots (q-1)}.$$

(8)

The subscript q of the Gaussian coefficient will be omitted without causing ambiguity in the following text.

The asymptotic behavior of the Gaussian coefficient is given by the following lemma.

Lemma 2 ([7]) Gaussian coefficient $\left[\begin{array}{c}n\\ k\end{array}\right]$, for $0<k<n$ satisfies:

$$1<q^{-k(n-k)}\left[\begin{array}{c}n\\ k\end{array}\right]<4.$$

(9)

We will introduce an important definition in combinatorial mathematics, which is very useful in our proof.

Let $\mathcal{J}$ be a collection of k-subsets of an n-set S, $0\le k\le n$. The collection:

$$\partial \mathcal{J}:=\{K\in \left(\genfrac{}{}{0pt}{}{S}{k-1}\right):K\subset J,forsomeJ\in \mathcal{J}\}$$

is called the shadow of $\mathcal{J}$, where $\left(\genfrac{}{}{0pt}{}{S}{k-1}\right)$ denotes the set of all $(k-1)$-subsets of S. That is, $\partial \mathcal{J}$ consists of all subsets of S, which can be obtained by deleting an element from a set in $\mathcal{J}$.

The lower bound of the size of a shadow is given by the Kruskal–Katona theorem [13,14]. Additionally, Lovász [15] proposed a weaker and simpler form of the original theorem. In [16], Lovász’s theorem is extended to vector spaces.

For a given n-dimensional vector space W, we define the shadow as follows.

Definition 4. Let $\mathcal{F}$ be a collection of k-dimensional subspaces of an n-dimensional vector space W, where $k<n$. The shadow of $\mathcal{F}$ is denoted by $\partial \mathcal{F}$,

$$\partial \mathcal{F}:=\{E\in \left[\begin{array}{c}W\\ k-1\end{array}\right]:E\subset F,forsomeF\in \mathcal{F}\},$$

where $\left[\begin{array}{c}W\\ k-1\end{array}\right]$ denotes the set of all $(k-1)$-dimensional subspaces of W.

A lower bound for the size of the shadow $\partial \mathcal{F}$ is shown in the following lemma.

Lemma 3 ([16]) Let $\mathcal{F}\subset \left[\begin{array}{c}W\\ k\end{array}\right]$, and let $y\ge k$ be the positive integer, which satisfies $\left|\mathcal{F}\right|=\left[\begin{array}{c}y\\ k\end{array}\right]$. Then, $\left|\partial \mathcal{F}\right|\ge \left[\begin{array}{c}y\\ k-1\end{array}\right]$. If equality holds, then $y\in {\mathbb{Z}}^{+}$ and $\mathcal{F}=\left[\begin{array}{c}Y\\ k\end{array}\right]$, where Y is a y-dimensional subspace of W.

We extend Lemma 3 to the case of l-level shadow. Let ${\partial }^{\left(l\right)}\mathcal{F}$ denote the l-level shadow of a collection of k-dimensional subspaces of W. Namely, similarly to the definition of $\partial \mathcal{F}$, we define:

$${\partial }^{\left(l\right)}\mathcal{F}:=\{E\in \left[\begin{array}{c}W\\ k-l\end{array}\right]:E\subset F,forsomeF\in \mathcal{F}\},$$

where $\left[\begin{array}{c}W\\ k-l\end{array}\right]$ denotes the set of all $(k-l)$-dimensional subspaces of W. For simplicity, the l-level shadow will be referred to as the l-shadow. The following lemma gives a lower bound of the size of the l-shadow.

Lemma 4. Let $\mathcal{F}\subset \left[\begin{array}{c}W\\ k\end{array}\right]$, and let $y\ge k$ be the positive integer, which satisfies $\left|\mathcal{F}\right|=\left[\begin{array}{c}y\\ k\end{array}\right]$. Then, $\left|{\partial }^{\left(l\right)}\mathcal{F}\right|\ge \left[\begin{array}{c}y\\ k-l\end{array}\right]$ for $k\ge l$. If equality holds, then $y\in {\mathbb{Z}}^{+}$ and $\mathcal{F}=\left[\begin{array}{c}Y\\ k\end{array}\right]$, where Y is a y-dimensional subspace of W.

Proof. Refer to Appendix A.1.

In Lemma 4, if the equality holds, there exists a y-dimensional subspace Y, such that ${\partial }^{\left(l\right)}\mathcal{F}$ is the set of all $(k-l)$-dimensional subspaces of Y, for $0\le l\le k$.

Since the cardinality of the set $\mathcal{F}$ is not exactly equal to a Gaussian coefficient in general, we extend Lemma 4 to a general case in the following corollary.

Corollary 1. Let $\mathcal{F}\subset \left[\begin{array}{c}W\\ k\end{array}\right]$ be a collection of k-dimensional subspaces of W and $\left|\mathcal{F}\right|\le \left[\begin{array}{c}y\\ k\end{array}\right]$, then $\left|{\partial }^{\left(l\right)}\mathcal{F}\right|\ge \frac{\left[\begin{array}{c}y\\ k-l\end{array}\right]}{\left[\begin{array}{c}y\\ k\end{array}\right]}\left|\mathcal{F}\right|.$

Proof. Refer to Appendix A.2.

Corollary 1 gives the lower bound for the size of an l-shadow of a given collection of subspaces, which will be used in the proof of our result.

Using the representation of combinatorial mathematics, we discuss the conditions for correctly decoding BECNC. Due to the packets lost, the receiver $t_1$ can receive a $(k-{\tau }_1)$-dimensional subspace $U_1\in {\partial }^{\left({\tau }_1\right)}\left\{V_{i,j}\right\}$, and the receiver $t_2$ can receive a $(k-{\tau }_2)$-dimensional subspace $U_2\in {\partial }^{\left({\tau }_2\right)}\left\{V_{i,j}\right\}$. We say that the receivers can decode correctly, if for $t_1$:

$${\partial }^{\left({\tau }_1\right)}\left\{V_{i,j}\right\}\cap {\partial }^{\left({\tau }_1\right)}\left\{V_{i^{\prime },j^{\prime }}\right\}=\varnothing ,if(i,j)\ne (i^{\prime },j^{\prime }),$$

(10)

and for $t_2$:

$${\partial }^{\left({\tau }_2\right)}\left\{V_{i,j}\right\}\cap {\partial }^{\left({\tau }_2\right)}\left\{V_{i^{\prime },j^{\prime }}\right\}=\varnothing ,ifi\ne i^{\prime },\forall j,j^{\prime }.$$

(11)

4.2. Outer Bound

We prove the outer bound of the achievable rate region at first. By Remark 1, it is sufficient to consider the deletion error correcting in the proof. Inspired by the analogues between the definition of shadow and the packing sphere of deletion-correcting codes, we adopt the concept of shadow in combinatorial theory. Furthermore, there is a lower bound for the size of the shadow in vector space [16]. A small generalization of the lower bound is provided in Corollary 1, which will be used in the proof of the outer bound.

Theorem 2. (Outer bound of the achievable rate region) If $(R_1,R_2)$ is an achievable rate pair of an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC, $\mathcal{C}\subset {\mathcal{P}}_q(n,k)$, for an x with $k\le x\le n$, then the following inequalities hold,

$$M_1\le \frac{\left[\begin{array}{c}n\\ k-{\tau }_2\end{array}\right]\left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]}{\left[\begin{array}{c}x\\ k-{\tau }_2\end{array}\right]\left[\begin{array}{c}x-1\\ k-{\tau }_1\end{array}\right]}$$

(12)

where x is the smallest integer, such that:

$$M_2\left[\begin{array}{c}k\\ k-{\tau }_1\end{array}\right]\le \left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]$$

(13)

In particular, if the equality of (13) holds, we have:

$$M_1\le \frac{\left[\begin{array}{c}n\\ k-{\tau }_2\end{array}\right]}{\left[\begin{array}{c}x\\ k-{\tau }_2\end{array}\right]}$$

(14)

We can obtain the asymptotic form of Theorem 2 directly.

Corollary 2. If $(R_1,R_2)$ is an achievable rate pair of an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC, $\mathcal{C}\subset {\mathcal{P}}_q(n,k)$, for an x with $k\le x\le n$, then the following inequalities hold,

$$\begin{array}{ccc}& R_1& \ge 0,R_2\ge 0\hfill \end{array}$$

(15)

$$\begin{array}{ccc}& R_1& \le \left(1-{\mu }_1\right)\left({\lambda }_x-\lambda \right),\hfill \end{array}$$

(16)

$$\begin{array}{ccc}& R_2& \le \left(1-{\mu }_2\right)\left(1-{\lambda }_x\right),\hfill \end{array}$$

(17)

where ${\lambda }_x=x/n,\lambda =k/n$ are the normalized weights and ${\mu }_1={\tau }_1/k,{\mu }_2={\tau }_2/k$ are the normalized deletion-correcting capabilities.

Proof of Theorem 2. Let $\mathcal{V}=\left\{V_{i,j}:i=1,2,\cdots ,M_1,j=1,2,\cdots ,M_2\right\}$ be the codebook of an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC that can correct ${\tau }_1$ and ${\tau }_2$ deletions for receivers $t_1$ and $t_2$, respectively, where $dim\left(V_{i,j}\right)=k,{\tau }_1<{\tau }_2<k$ and $\delta ={\tau }_2-{\tau }_1$.

For fixed i, we denote the ${\tau }_1$-shadow of the codeword $V_{i,j}$ as ${\partial }^{\left({\tau }_1\right)}\left\{V_{i,j}\right\}$; then, the ${\tau }_1$-shadows of $V_{i,j},j=1,2,\cdots ,M_2$ are disjoint, namely:

$${\partial }^{\left({\tau }_1\right)}\left\{V_{i,j}\right\}\cap {\partial }^{\left({\tau }_1\right)}\left\{V_{i,j^{\prime }}\right\}=\varnothing ,$$

and the cardinality of each shadow is $|{\partial }^{\left({\tau }_1\right)}\left\{V_{i,j}\right\}|=\left[\begin{array}{c}k\\ k-{\tau }_1\end{array}\right]$. We denote the set of these shadows as $SH\left(i\right)=\{{\partial }^{\left({\tau }_1\right)}\left\{V_{i,j}\right\}:j=1,2,\cdots ,M_2\}$; then, $\left|SH\left(i\right)\right|=M_2\left[\begin{array}{c}k\\ k-{\tau }_1\end{array}\right]$.

Figure 2 illustrates the relationship of ${\tau }_1$-shadows when i is fixed. The big dotted line circle on the top level denotes the set of codewords, in which small solid circles denote the codewords. The small solid circle on the middle level denotes the ${\tau }_1$-level shadow of a codeword, while the big dotted line circle on the middle level denotes the set of the ${\tau }_1$-level shadow. Similarly, a small solid circle on the bottom level denotes the ${\tau }_2$-level shadow of a codeword, while the big dotted line circle on the bottom level denotes the set of ${\tau }_2$-level shadows.

Figure 2. The relationship of ${\tau }_1$-shadows when i is fixed.

Figure 2. The relationship of ${\tau }_1$-shadows when i is fixed.

For $i\ne i^{\prime }$ and any $j,j^{\prime }$,

$${\partial }^{\left(\delta \right)}{\partial }^{\left({\tau }_1\right)}\left\{V_{i,j}\right\}\cap {\partial }^{\left(\delta \right)}{\partial }^{\left({\tau }_1\right)}\left\{V_{i^{\prime },j^{\prime }}\right\}=\varnothing ,$$

because otherwise,

$${\partial }^{\left({\tau }_2\right)}\left\{V_{i,j}\right\}\cap {\partial }^{\left({\tau }_2\right)}\left\{V_{i^{\prime },j^{\prime }}\right\}\ne \varnothing ,$$

which is contradictory to Condition (11). That is, the δ-shadows of $SH\left(i\right)$ and $SH\left(i^{\prime }\right)$ are disjoint for all $i\ne i^{\prime }$. From Corollary 1, we can get the minimum size of the δ-shadow of $SH\left(i\right)$, which is bounded by $\left|{\partial }^{\left(\delta \right)}SH\left(i\right)\right|\ge \frac{\left[\begin{array}{c}x\\ k-{\tau }_2\end{array}\right]}{\left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]}\left|SH\left(i\right)\right|$, and $x\ge k-{\tau }_2$ is the minimum integer, such that $\left|SH\left(i\right)\right|\le \left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]$.

Then, we can get $M_2\left[\begin{array}{c}k\\ k-{\tau }_1\end{array}\right]\le \left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]$, and:

$$M_2\le \frac{\left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]}{\left[\begin{array}{c}k\\ k-{\tau }_1\end{array}\right]}\stackrel{\left(a\right)}{<}\frac{4q^{\left(k-{\tau }_1\right)\left(x-k+{\tau }_1\right)}}{q^{(k-{\tau }_1)\left(k-k+{\tau }_1\right)}}=4q^{\left(k-{\tau }_1\right)\left(x-k\right)}.$$

(18)

The inequality (a) holds according to Lemma 2.

Now, we consider the cardinality of ${\partial }^{\left(\delta \right)}SH\left(i\right)$,

$$\begin{array}{cc}\hfill \left|{\partial }^{\left(\delta \right)}SH\left(i\right)\right|& \ge \frac{\left[\begin{array}{c}x\\ k-{\tau }_2\end{array}\right]}{\left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]}\left|SH\left(i\right)\right|\stackrel{\left(b\right)}{\ge }\frac{\left[\begin{array}{c}x\\ k-{\tau }_2\end{array}\right]}{\left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]}\left[\begin{array}{c}x-1\\ k-{\tau }_1\end{array}\right].\end{array}$$

(19)

The inequality (b) holds since x is the minimum integer, such that $\left|SH\left(i\right)\right|\le \left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]$, and the Gaussian coefficient $\left[\begin{array}{c}n\\ k\end{array}\right]$ is monotone increasing with n.

By packing, $M_1$ is bounded by:

$$\begin{array}{ccc}\hfill M_1& \le & \frac{\left[\begin{array}{c}n\\ k-{\tau }_2\end{array}\right]}{\left|{\partial }^{\left(\delta \right)}SH\left(i\right)\right|}\le \frac{\left[\begin{array}{c}n\\ k-{\tau }_2\end{array}\right]\left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]}{\left[\begin{array}{c}x\\ k-{\tau }_2\end{array}\right]\left[\begin{array}{c}x-1\\ k-{\tau }_1\end{array}\right]}\hfill \end{array}$$

$$\begin{array}{ccc}& \stackrel{\left(c\right)}{<}& \frac{16q^{\left(k-{\tau }_2\right)\left(n-k+{\tau }_2\right)+\left(k-{\tau }_1\right)\left(x-k+{\tau }_1\right)}}{q^{\left(k-{\tau }_2\right)\left(x-k+{\tau }_2\right)+\left(k-{\tau }_1\right)\left(x-1-k+{\tau }_1\right)}}\hfill \end{array}$$

$$\begin{array}{ccc}& =& 16q^{\left(k-{\tau }_2\right)\left(n-x\right)+\left(k-{\tau }_1\right)}.\hfill \end{array}$$

(20)

The inequality (c) holds according to Lemma 2.

Then, the rate pair of $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC, $\mathcal{C}\subset {\mathcal{P}}_q(n,k)$, satisfies:

$$\begin{array}{ccc}\hfill R_1& =& \frac{{log}_q{M}_2}{nk}\le \frac{\left(k-{\tau }_1\right)\left(x-k\right)}{nk}+o\left(1\right)\hfill \end{array}$$

$$\begin{array}{ccc}& =& \left(1-{\mu }_1\right)\left({\lambda }_x-\lambda \right)+o\left(1\right)\hfill \end{array}$$

(21)

and:

$$\begin{array}{ccc}\hfill R_2& =& \frac{{log}_q{M}_1}{nk}\le \frac{\left(k-{\tau }_2\right)\left(n-x\right)+\left(k-{\tau }_1\right)}{nk}+o\left(1\right)\hfill \end{array}$$

$$\begin{array}{ccc}& =& \left(1-{\mu }_2\right)\left(1-{\lambda }_x\right)+o\left(1\right),\hfill \end{array}$$

(22)

where $o\left(1\right)$ approaches zero as n grows, and x is an auxiliary variable, such that $k\le x\le n$. The normalized weights are ${\lambda }_x=x/n,\lambda =k/n$, and the normalized deletion-correcting capabilities are ${\mu }_1={\tau }_1/k,{\mu }_2={\tau }_2/k$.

This completes the proof of the outer bound. ☐

4.3. Achievability

In this section, we propose a construction of BECNC based on superposition coding, with which the achievability of our outer bound can be proven. If the rate pair $(R_1,R_2)$ is achievable, then the code used at each level must satisfy certain properties, which are specified below.

Construction: Let ${\mathbb{F}}_q^n$ be an n-dimensional vector space over ${\mathbb{F}}_q$ and x be an integer, such that $k\le x\le n$. We can construct an x-dimensional constant dimension subspace code ${\mathcal{C}}_x$ over ${\mathbb{F}}_q^n$ for $t_1$ and $t_2$, such that it can correct deletions of $x-k+{\tau }_2$. The encoding mapping is $\widehat{f}$, and the decoding mappings at $t_1$ and $t_2$ are $\widehat{\phi }$ and $\widehat{\psi }$, respectively.

The codeword $\widehat{f}\left(i\right)$ can be regarded as the cloud center, which will not be actually sent. For every $i\in {\mathcal{M}}_1$, the $(x-k+{\tau }_2)$-shadows of $\left\{\widehat{f}\left(i\right)\right\}$ are disjoint, namely,

$${\partial }^{(x-k+{\tau }_2)}\left\{\widehat{f}\left(i\right)\right\}\cap {\partial }^{(x-k+{\tau }_2)}\left\{\widehat{f}\left(i^{\prime }\right)\right\}=\varnothing ,fori\ne i^{\prime },$$

(23)

which guarantees the correctness of decoding at $t_2$. The rate of ${\mathcal{C}}_x$ is:

$$\frac{1}{nx}log\left|{\mathcal{M}}_1\right|.$$

(24)

Additionally, for every $i\in {\mathcal{M}}_1$, the $(x-k+{\tau }_1)$-shadow of $\left\{\widehat{f}\left(i\right)\right\}$ must be disjoint; otherwise, the $({\tau }_2-{\tau }_1)$-shadow of the $(x-k+{\tau }_1)$-shadow of $\left\{\widehat{f}\left(i\right)\right\}$ will have a common subset. That is,

$${\partial }^{(x-k+{\tau }_1)}\left\{\widehat{f}\left(i\right)\right\}\cap {\partial }^{(x-k+{\tau }_1)}\left\{\widehat{f}\left(i^{\prime }\right)\right\}=\varnothing ,fori\ne i^{\prime },$$

(25)

which guarantees the correctness of decoding at $t_1$.

Let $A\left(i\right)$ be the $(x-k)$-shadow of a codeword $\widehat{f}\left(i\right)$, i.e.,

$$A\left(i\right)={\partial }^{(x-k)}\left\{\widehat{f}\left(i\right)\right\},$$

(26)

the shadows $A\left(i\right),i\in {\mathcal{M}}_1$ are disjoint by construction of code ${\mathcal{C}}_x$.

To every $i\in {\mathcal{M}}_1$, by using $\widehat{f}\left(i\right)$ as the ground space, we can construct a k-dimensional subspace code $\mathcal{C}\subseteq A\left(i\right)$ for $t_1$, such that it can correct deletions of ${\tau }_1$. For each i, the code has the same message set ${\mathcal{M}}_2$. The encoding mapping is $f_i$, and the decoding mapping is ${\phi }_i$; the rate of $\mathcal{C}$ is:

$$\frac{1}{xk}log\left|{\mathcal{M}}_2\right|.$$

(27)

The codewords of $\mathcal{C}$ will be actually sent, which can be regarded as a satellite codeword. For every $i\in {\mathcal{M}}_1,j\in {\mathcal{M}}_2$, the ${\tau }_1$-shadows of $\left\{f_i\left(j\right)\right\}$ are disjoint, namely,

$${\partial }^{\left({\tau }_1\right)}\left\{f_i\left(j\right)\right\}\cap {\partial }^{\left({\tau }_1\right)}\left\{f_{i^{\prime }}\left(j^{\prime }\right)\right\}=\varnothing ,for(i,j)\ne (i^{\prime },j^{\prime }),$$

(28)

which guarantees the correctness of decoding at $t_1$.

The encoding mapping:

$$f:{\mathcal{M}}_1\times {\mathcal{M}}_2\to \mathcal{P}(n,k),$$

and the decoding mapping:

$$\phi :\mathcal{P}(n,k-{\tau }_1)\to {\mathcal{M}}_1\times {\mathcal{M}}_2,$$

and:

$$\psi :\mathcal{P}(n,k-{\tau }_2)\to {\mathcal{M}}_1,$$

are as follows:

$$\begin{array}{ccc}\hfill f(i,j)& =& f_i\left(j\right),foreveryi\in {\mathcal{M}}_1,j\in {\mathcal{M}}_2,\hfill \end{array}$$

$$\begin{array}{ccc}\hfill \phi \left(V_{r1}\right)& =& (i,{\phi }_i\left(V_{r1}\right)),wherei=\widehat{\phi }\left(V_{r1}\right),\hfill \end{array}$$

$$\begin{array}{ccc}\hfill \psi \left(V_{r2}\right)& =& \widehat{\psi }\left(V_{r2}\right),\hfill \end{array}$$

where $V_{r1}\in \mathcal{P}(n,k-{\tau }_1)$ and $V_{r2}\in \mathcal{P}(n,k-{\tau }_2)$ are the subspaces received by node $t_1$ and $t_2$, respectively.

We do not specify the code ${\mathcal{C}}_x$ and $\mathcal{C}$ used at each level in the above construction. The achievability of our outer bound could be proven if the subspace code used at each level satisfies some properties.

Proposition 1. For an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC, our outer bound could be achieved at $(R_1,R_2)$ asymptotically by the above construction, if there exists an $(n,k,M,\tau )$-deletion-correcting code for single-user communication, such that the code rate $R=(1-\mu )(1-\lambda )$ is asymptotically achievable.

Proof. If there exists such an asymptotically-achievable code, we can substitute this code for ${\mathcal{C}}_x$ and $\mathcal{C}$ in the above construction, where the parameters are $(n,x,M_1,x-k+{\tau }_2)$ and $(x,k,M_2,{\tau }_1)$, respectively.

The rate pair is:

$$\begin{array}{ccc}\hfill \frac{{log}_q\left|{\mathcal{M}}_2\right|}{nk}& \ge & \frac{xk(1-{\mu }_k)(1-{\lambda }_k)}{nk}-ϵ\hfill \end{array}$$

$$\begin{array}{ccc}& =& (1-{\mu }_1)({\lambda }_x-\lambda )-ϵ,\hfill \end{array}$$

(29)

$$\begin{array}{ccc}\hfill \frac{{log}_q\left|{\mathcal{M}}_1\right|}{nk}& \ge & \frac{nx(1-{\mu }_x)(1-{\lambda }_x)}{nk}-ϵ\hfill \end{array}$$

$$\begin{array}{ccc}& =& (1-{\mu }_2)(1-{\lambda }_x)-ϵ,\hfill \end{array}$$

(30)

where ${\mu }_k={\tau }_1/k,{\mu }_x=\frac{x-k+{\tau }_2}{x},{\lambda }_k=k/x,{\mu }_1={\tau }_1/k,{\mu }_2={\tau }_2/k,\lambda =k/n$, ${\lambda }_x=x/n$ and $ϵ>0$.

That is, the rate pair $(R_1,R_2)$:

$$\begin{array}{ccc}\hfill R_1& =& (1-{\mu }_1)({\lambda }_x-\lambda ),\hfill \end{array}$$

(31)

$$\begin{array}{ccc}\hfill R_2& =& (1-{\mu }_2)(1-{\lambda }_x),\hfill \end{array}$$

(32)

is asymptotically achievable. ☐

Fortunately, K-K codes satisfy the requirement in Proposition 1. From the minimum distance decoder requirements in Condition (4), we can rewrite Equation (2) in the form of deletion-correcting capability τ,

$$R\le (1-\mu )(1-\lambda )+o\left(1\right),$$

(33)

where $\mu =\tau /k$ is normalized deletion-correcting capability.

The achievability of outer bound can be obtained subsequently.

Theorem 3. (Achievability) If for a rate pair $(R_1,R_2)$ of nonnegative numbers, there exists an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC, $\mathcal{C}\subset {\mathcal{P}}_q(n,k)$, such that the following inequalities hold,

$$\begin{array}{ccc}& R_1& \ge 0,R_2\ge 0\hfill \end{array}$$

(34)

$$\begin{array}{ccc}& R_1& \le \left(1-{\mu }_1\right)\left({\lambda }_x-\lambda \right),\hfill \end{array}$$

(35)

$$\begin{array}{ccc}& R_2& \le \left(1-{\mu }_2\right)\left(1-{\lambda }_x\right),\hfill \end{array}$$

(36)

where x is an auxiliary variable, such that $k\le x\le n$. The normalized weights are ${\lambda }_x=x/n,\lambda =k/n$, and the normalized deletion-correcting capabilities are ${\mu }_1={\tau }_1/k,{\mu }_2={\tau }_2/k$. Then, $(R_1,R_2)$ is an achievable rate pair for the $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC.

Proof. The theorem can be proven by specifying the K-K codes to our construction.☐

5. Exactly Attained Codes

So far, the asymptotically-achievable rate region of BECNC is obtained by using K-K codes in our construction. However, the K-K codes achieve the Singleton-type bound in Equation (33) asymptotically, which requires the dimension of ground space n sufficiently large. In this section, we study the case when our outer bound can be attained exactly.

Proposition 2. For an $[n,k,(M_1,M_2),({\tau }_1,{\tau }_2)]$-BECNC, our outer bound could be achieved at $(M_1,M_2)$, if there exists an $(n,k,M,\tau )$-code for single-user communication, such that:

$$M=\frac{\left[\begin{array}{c}n\\ k-\tau \end{array}\right]}{\left[\begin{array}{c}k\\ k-\tau \end{array}\right]}.$$

(37)

The proof of this proposition will be given later.

The q-analog Steiner structure [19] could be used in the construction that was presented in Section 4.3, which does not require the size of n. We will state it in detail in the following.

A collection $\mathbb{S}\subseteq {\mathcal{P}}_q(n,k)$ is called a q-analog Steiner structure $\mathbb{S}{[t,k,n]}_q$ if the elements of $\mathbb{S}$ are k-dimensional subspaces (called blocks), and each element from ${\mathcal{P}}_q(n,t)$ is contained in exactly one block from $\mathbb{S}$. $\mathbb{S}{[t,n,n]}_q$ and $\mathbb{S}{[t,t,n]}_q$ exist, but these are trivial. Until recently, the only known nontrivial Steiner structures $\mathbb{S}{[1,k,n]}_q$ exist when k divides n. The problem of the existence of a Steiner structure with various parameters is still open. We do not concentrate on the existence of the q-analog Steiner structure in this paper. The constructions and properties of the q-analog Steiner structure are further discussed in [20].

We assume that there exists a q-Steiner structure $\mathbb{S}{[t,k,n]}_q$. This structure could be considered as a k-dimensional subspace code $\mathcal{C}$ over ${\mathbb{F}}_q^n$ with deletion-correcting capability $\tau =k-t$, where each block of $\mathbb{S}{[t,k,n]}_q$ is a codeword of $\mathcal{C}$. Since a codeword V produces a random $(k-\tau )$-dimensional subspace of V by the operation ${\mathcal{D}}_{\tau }$, the definition of the q-Steiner structure guarantees that each $(k-\tau )$-dimensional subspace corresponds to exactly one k-dimensional subspace in $\mathcal{C}$, i.e., every $(k-\tau )$-dimensional subspace can be correctly decoded into a transmitted subspace. The number of codewords of a q-Steiner structure $\mathbb{S}{[t,k,n]}_q$ is given by the number of blocks in $\mathbb{S}$.

Lemma 5 ([19]) The total number of blocks in an $\mathbb{S}{[t,k,n]}_q$ is:

$$\frac{\left[\begin{array}{c}n\\ t\end{array}\right]}{\left[\begin{array}{c}k\\ t\end{array}\right]}.$$

Then, the q-Steiner structure $\mathbb{S}{[k-\tau ,k,n]}_q$ could be regarded as an $(n,k,M,\tau )$-code, which satisfies Condition (37). Since the size of the codewords is:

$${M=|\mathbb{S}[k-\tau ,k,n]}_q|=\frac{\left[\begin{array}{c}n\\ k-\tau \end{array}\right]}{\left[\begin{array}{c}k\\ k-\tau \end{array}\right]}.$$

(38)

Proof of Proposition 2. Similar to the proof of Proposition 1. We could substitute the q-Steiner structure $\mathbb{S}{[k-{\tau }_2,x,n]}_q$ and $\mathbb{S}{[k-{\tau }_1,k,x]}_q$ for ${\mathcal{C}}_x$ and $\mathcal{C}$ in the construction in Section 4.3, respectively. The numbers of codewords are:

$$\begin{array}{ccc}\hfill M_2& =& |\mathbb{S}{[k-{\tau }_1,k,x]}_q|=\frac{\left[\begin{array}{c}x\\ k-{\tau }_1\end{array}\right]}{\left[\begin{array}{c}k\\ k-{\tau }_1\end{array}\right]},\hfill \end{array}$$

(39)

$$\begin{array}{ccc}\hfill M_1& =& |\mathbb{S}{[k-{\tau }_2,x,n]}_q|=\frac{\left[\begin{array}{c}n\\ k-{\tau }_2\end{array}\right]}{\left[\begin{array}{c}x\\ k-{\tau }_2\end{array}\right]},\hfill \end{array}$$

(40)

which coincide with Equation (13) and Equation (14) when the equalities hold. That is, the rate pair $(M_1,M_2)$ in Theorem 2 is exactly attained.

Note that, because of the number of the known q-Steiner structure is very limited, the exactly attained codes of BECNC cannot achieve all of the points in the rate region of Theorem 1. It will be of interest to study the existence of the q-Steiner structure.

6. Extension

In this section, we will extend the asymptotically-achievable rate region to more than two receivers. Consider the model depicted in Section 2.2; we can obtain the asymptotically-achievable rate region of the m-tuple coding rates $(R_1,R_2,\cdots ,R_m)$.

Theorem 4. The asymptotically-achievable rate region of an $[n,k,(M_1,M_2,\cdots ,M_m),({\tau }_1,{\tau }_2,\cdots ,{\tau }_m)]$-BECNC with corresponding error correcting-capabilities ${\tau }_1,{\tau }_2,\cdots ,{\tau }_m$ over field ${\mathbb{F}}_q$ consists of rates $(R_1,R_2,\cdots ,R_m)$ of non-negative numbers that satisfy the inequalities,

$$\begin{array}{ccc}& R_1& \ge 0,R_2\ge 0,\cdots ,R_m\ge 0\hfill \end{array}$$

(41)

$$\begin{array}{ccc}& R_1& \le \left(1-{\mu }_1\right)({\lambda }_1-\lambda ),\hfill \end{array}$$

(42)

$$\begin{array}{ccc}& R_2& \le \left(1-{\mu }_2\right)({\lambda }_2-{\lambda }_1),\hfill \end{array}$$

(43)

$$\begin{array}{ccc}& \cdots & \end{array}$$

(44)

$$\begin{array}{ccc}& R_m& \le \left(1-{\mu }_m\right)(1-{\lambda }_{m-1}),\hfill \end{array}$$

(45)

where $x_1,\cdots ,x_{m-1}$ are auxiliary variables, such that $k\le x_1\le \cdots \le x_{m-1}\le n$. The normalized weights are ${\lambda }_i=x_i/n,\lambda =k/n,i=1,\cdots ,m-1$, and the normalized error-correcting capabilities are ${\mu }_i={\tau }_i/k,i=1,\cdots ,m$.

The proof can refer to the steps from the proofs of Theorem 1, where we leave it for the readers as an exercise.

7. Conclusion

In this paper, we propose a network model based on a real-time media distribution system, where the receivers have different link capacities due to packets lost or a fault in intermediate nodes. To solve the transmission problem in our model, we provide the broadcast error-correcting network codes (BECNC), which are based on subspace metric codes. Then, we present the asymptotically-achievable rate region for BECNC. In the proof part, we show the outer bound of the achievable rate region, followed by a code construction. We prove that the outer bound is asymptotically achieved by specifying K-K codes in our construction. Meanwhile, the outer bound is exactly attained by using the q-analog Steiner structure in our construction. Since the number of the known q-analog Steiner structure is limited, the outer bound can be attained exactly in some points. The research on the existence and construction of q-analog Steiner structures may be interesting. Although K-K codes require the dimension of ground space n sufficiently large and the known q-analog Steiner structure is limited, the theoretical rate region given in this paper has certain practical significance. In the future, if we could find the “good” codes, this outer bound could be attained exactly at all points.