JP7632741B2 - Encoding device, encoding method, and program - Google Patents

Description

The present invention relates to a technology for communicating correctly with a small probability of decoding error in a noisy environment.

One example of a technique for communicating correctly with a small probability of decoding errors in a noisy environment is the technique disclosed in Non-Patent Document 1. Non-Patent Document 1 discloses a method for implementing coding in a communication channel with many input/output terminals.

Jun Muramatsu, Shigeki Miyake,"Multi-Terminal Codes Using Constrained-Random-Number Generators", https://arxiv.org/pdf/1801.02875.pdf

In a communication channel with multiple input/output terminals, the structure that indicates which of multiple messages multiple encoders input and encode is called the message access structure.

In today's communication environment where there are many information sources, it is desirable to realize efficient encoding for any access structure. However, conventional techniques such as the technique disclosed in Non-Patent Document 1 were not able to efficiently encode for any access structure.

The present invention has been made in consideration of the above points, and aims to provide a technology that enables efficient encoding for any access structure in a communication path with multiple input/output terminals.

According to the disclosed technology, there is provided an encoding device in a communication system including a set of encoding devices that perform encoding in a communication path having a plurality of input/output terminals, the encoding device comprising:
A receiving unit for receiving a message;
a control unit configured to generate code words from messages received by the receiving unit based on a classification result obtained by classifying a plurality of messages according to a subset of the encoding devices that can access the messages;
An encoding device is provided, comprising:

The disclosed technology makes it possible to efficiently encode any access structure in a communication channel with multiple input/output terminals.

1 is a diagram illustrating an example of a configuration of a communication system according to an embodiment of the present invention. FIG. 13 is a diagram illustrating an example 1 of an access structure. FIG. 11 is a diagram illustrating an example 2 of an access structure. FIG. 1 is a diagram showing Algorithm 1. FIG. 2 is a diagram showing the internal processing contents of an encoding device. FIG. 2 is a diagram showing the internal processing contents of a decoding device. FIG. 2 is a diagram showing Algorithm 2. FIG. 1 illustrates an example of an apparatus configuration. FIG. 2 illustrates an example of a hardware configuration of the apparatus.

An embodiment of the present invention (the present embodiment) will be described below with reference to the drawings. The embodiment described below is merely an example, and the embodiment to which the present invention is applied is not limited to the embodiment described below. In the following description, references are represented by numbers such as [1], and the names of the documents corresponding to the numbers are listed at the end of the specification.

(overview)
As described above, in a modern communication environment in which a large number of information sources exist, it is desirable to realize efficient coding for an arbitrary access structure. However, in conventional techniques such as the technique disclosed in Non-Patent Document 1, it is not possible to efficiently code for an arbitrary access structure.

More specifically, in a configuration like Fig. 4 in [3], in a general access structure corresponding to Fig. 1 and Example 2 described later, when the auxiliary random variable Z ⁿ _S (in Fig. 4 of [3]) is assumed to be stationary and memoryless, efficient communication cannot be performed. In addition, when a communication channel W _i (in Fig. 4 of [3]) with the same dimension as the block length n is configured, the complexity of the system configuration and the calculation time become large.

In addition, in relation to a method for implementing an encoding method in a communication channel with many input/output terminals when the message access structure is arbitrary, the prior art only had simple methods for cases where there is a one-to-one correspondence between independent message sets and encoders, or where there is a common message set for all codes as in Fig. 8 of literature [4], and in order to realize efficient communication in this case, a complex configuration was required. In other words, the prior art was not able to efficiently encode for an arbitrary access structure.

Below, we describe a technology that enables efficient encoding for any access structure without using complex structures.

In this embodiment, a technique for encoding on a communication channel with two or more input/output terminals (multi-terminal communication channel) is described. In particular, in this embodiment, messages are classified according to "the set of encoders that can access them," and each encoder performs encoding by generating random numbers in an order sorted according to the inclusion relationship of the set of encoders (for example, from largest to smallest).

The encoder and decoder are constructed using a random number generator and a sparse matrix that satisfy the constraints. However, using a random number generator that satisfies the constraints is just one example, and encoding and decoding can be achieved using any appropriately defined transformation other than random number generation that satisfies the constraints.

In the following, a device that performs encoding will be referred to as an encoding device, and a device that performs decoding will be referred to as a decoding device. The encoding device and the decoding device may also be referred to as an encoder and a decoder, respectively.

(Example of overall configuration of communication system)
An example of the overall configuration of a communication system according to the present embodiment is shown in Fig. 1. As shown in Fig. 1, this communication system includes a plurality of encoding devices and a plurality of decoding devices, which are connected to a communication network (which may also be called a communication path).

In Figure 1, M indicates a message, Φ indicates an encoding process, X indicates input information to the communication channel (output information from the encoding device), μ indicates characteristics of the communication channel, Y indicates output information from the communication channel (input information to the decoding device), Ψ indicates a decoding process, and ^M indicates a message output from the decoding device; details of these will be given later. Note that "^M" in the specification text is intended to be the symbol with a hat at the beginning of M.

Each encoding device has multiple input interfaces (which may also be called input terminals) as a receiving unit, and is capable of inputting multiple messages. In this embodiment, inputting a message into an encoding device may also be expressed as "the encoding device accessing a message."

(Definition and Notation)
Here, we will explain the definitions and notations used in the description of the present embodiment. The German letters I and L in the formulas and algorithms shown in the drawings or images in the specification will be expressed as ^〜 I and ^〜 L, respectively, in the specification text. In addition, when the notation method in the image differs from the notation method in the specification text, the content will be explained appropriately unless it is so obvious that explanation is not necessary.

In the following, when the notation u _V ≡{u _v } _u∈V is used, it means a set of u _v (sequences, random variables, functions, etc.) with v belonging to set V as an index. |V| represents the number of elements in set V. Note that {u _v } _v∈V is not a set (which does not allow duplications), but is called an associative array (hash, dictionary) that has a value u _v for one v. Also, {u _n } ^∞ _n=1 means a sequence {u _n ; n=1, 2, ...}.

Let I be the set of channel inputs and the corresponding encoder indices. Let J be the set of channel outputs and the corresponding decoder indices. A general channel is a sequence of conditional probability distributions

で表される。ここでＸ^ｎ _Ｉ≡｛Ｘ^ｎ _ｉ｝_ｉ∈Ｉは通信路入力の確率変数であり、Ｙ^ｎ _Ｊ≡｛Ｙ^ｎ _ｊ｝_ｊ∈Ｊは通信路出力の確率変数である。つまり、Ｘ^ｎ _Ｉは、符号化装置（の集合）から出力される情報（データ、信号）を示す。Ｙ^ｎ _Ｊは、復号装置（の集合）へ入力される情報（データ、信号）を示す。

Here, ^XnI ≡ { ^Xni } _i∈I is a random variable of _the communication channel input, _and ^YnJ ≡ { ^Ynj } _j∈J is a random variable of _the communication channel output. In other words, ^XnI represents information (data, signal) output from _{( a} set of) encoding devices _. ^YnJ represents information (data, signal) input to (a set of) decoding devices.

For each i∈I, let XX ⁿ _i be the set of possible values (hereafter referred to as the alphabet) of the random variable X ⁿ _i ≡ (X _i,1 , ..., X _i,n ). Note that a notation such as "XX" in which two capital letters are written side by side corresponds to the single letter "X" in cursive writing in drawings and images.

Here, the natural number n is the block length, and XX ⁿ _i is the n-dimensional Cartesian product of sets XX _i . For each j∈J, let YY ⁿ _j be the alphabet of random variables Y ⁿ _j , where YY ⁿ _j need not be an n-dimensional space.

Let S be a set of message indices. For each s∈S, let M _s be the s-th message (hereafter called message s) that follows a uniform distribution on the alphabet MM _s . Assume that {M _s } _s∈S are mutually independent. Note that the assumption of uniformity and independence may not be made.

The i-th encoder (hereafter referred to as encoder i) receives a message set M _S(i) ≡ {M _s } _{s ∈ S(i)} , converts (encodes) it, and transmits X ⁿ _i as a channel input, where S(i) is a set of indexes of messages that encoder i can access, and will be described in detail later.

For each j∈J, let D(j) be the index set of messages that the jth decoder (hereafter called decoder j) reproduces (decodes), where D(j) ⊂ S. The decoder j receives the channel output Y ⁿ _j and reproduces (decodes) the reproduced message

を求める。ここで＾Ｍ_ｊ，ｓ∈ＭＭ_ｓは復号装置ｊによって再生されたメッセージｓである。本実施の形態では、ブロック長ｎを十分大きくとることにより、任意のｊ∈Ｊとｓ∈Ｄ_ｊで＾Ｍ_ｊ，ｓ＝Ｍ_ｓが成立する確率が１に近いような符号化装置／復号装置を構成する。＾Ｍ_ｊ，ｓ＝Ｍ_ｓが成立する確率が１に近いということは、復号誤り確率が小さいということである。すなわち、本実施の形態において構成した符号はＰｒｏｂ（・）を事象の確率を表すとき、任意のε＞０に対して十分大きなｎをとることにより、

Here, ^Mj _,s ∈ _MMs is the message s reproduced by the decoder j. In this embodiment, by setting the block length n to be sufficiently large, an encoding device/decoding device is configured in which the probability that ^Mj _{,s = Ms} holds for any j∈J and s∈Dj is close to 1. The fact that the probability that ^Mj _,s = _Ms holds close to 1 means that the decoding error probability is small. In other words, when Prob(.) represents the probability of an event, the code constructed in this embodiment can be expressed as follows by setting n to be sufficiently large for any ε>0:

を満たしている。上式の左辺は復号誤り確率と呼ばれる。以降の説明において、Ｈの下にバーが付いた文字を明細書テキストでは「下バーＨ」と表記し、Ｈの上にバーが付いた文字を明細書テキストでは「上バーＨ」と表記する。

The left side of the above equation is called the decoding error probability. In the following description, the character with a bar below H will be written as "H with a bar below" in the specification text, and the character with a bar above H will be written as "H with a bar above" in the specification text.

Distribution sequence of random variables U≡{U _n } ^∞ _n=1

を与えたとき、下バーＨ（Ｕ）を条件付きスペクトルエントロピーレート下限とする。確率変数（Ｕ，Ｖ）≡｛（Ｕ_ｎ，Ｖ_ｎ）｝^∞ _ｎ＝１の分布列

Let H(U) be the conditional lower bound for the spectral entropy rate. The distribution sequence of random variables (U, V) ≡ {(U _n , V _n )} ^∞ _{n = 1}

を与えたとき、下バーＨ（Ｕ｜Ｖ）、上バーＨ（Ｕ｜Ｖ）をそれぞれ、スペクトルエントロピーレート下限、スペクトルエントロピーレート上限とする。これらについての形式的な定義については後述する。

Let H(U|V) be the lower bound of the spectral entropy rate and H(U|V) be the upper bound of the spectral entropy rate. The formal definitions of these will be given later.

Here, when the sequence of random variables is stationary and memoryless (independent and identically distributed), H(U) becomes the entropy H(U), and both H(U|V) and H(U|V) become the conditional entropy H(U|V). Also, when the sequence of random variables {U ⁿ } ^∞ _n=1 , {(U ⁿ , V ⁿ )} ^∞ _n=1 only has stationarity, H(U) becomes the entropy rate lim _n→∞ H(U ⁿ )/n, and both H(U|V) and H(U|V) become the conditional entropy rate lim _n→∞ H(U ⁿ |V ⁿ )/n.

For each s∈S, let ZZ ⁿ _s be the alphabet of random variables Z ⁿ _s . Here, ZZ ⁿ s does not need to be an n-dimensional space. For each s∈S, let CC _s be a set that is the range of a function f _s described below. Let c _s ∈CC _s and m _s ∈MM _s , and hereafter c _s and m _s will be called vectors.

を各々、関数の集合とする。ｃ_Ｓ≡｛ｃ_ｓ｝_ｓ∈Ｓ，ｍ_Ｓ≡｛ｍ_ｓ｝_ｓ∈Ｓを各々、ベクトルの集合とする。Ｓの部分集合Ｓ′を与えたとき、

Let c _S ≡ {c _s } _{s ∈ S} , m _S ≡ {m _s } _{s ∈ S} be sets of vectors. Given a subset S' of S,

と定義する。ここで、ｚ_ｓ∈ＺＺ^ｎ _ｓ，ｚ_Ｓ′≡｛ｚ_ｓ｝_ｓ∈Ｓ′である。関数χ（Ｓ）を以下のように定義する。

Here, _{zs ∈} ^ZZns , zS _' ≡ { _zs } _{s ∈ S'} . The function χ(S) is defined as follows.

（アクセス構造について）
アクセス構造とは、例として図２、図３に示すように、符号化装置がどのメッセージを入力とするか（どのメッセージにアクセスできるか）を示す情報である。より詳細には下記のとおりである。

(Regarding access structure)
The access structure is information indicating which messages the encoding device receives as input (which messages it can access), as shown in Figures 2 and 3. More specifically, it is as follows.

The access structure A is a subset of S×I, and (s, i) ∈ A means that the encoding device i can access the message s. If A is interpreted as a set of directed edges and (s, i) ∈ A as the directed edge s → i, then (S, I, A) becomes a bipartite graph. Figures 2 and 3 show that a bipartite graph is constructed between the messages and the encoding devices.

For each s∈S, let I(s) be the set of indices of encoders that can access message s.

I(s)≡{i∈I:(s,i)∈A}
For each i ∈ I, let S(i) be the set of indices of messages that encoder i has access to.

S(i)≡{s∈S:(s,i)∈A}
Here, i ∈ I(s) and s ∈ S(i) are equivalent.

Let I' be a subset of I. For each I', let S(I') be the index set of messages shared by index set I' and the corresponding encoder.

S(I′)≡{s∈S:I(s)=I′}
^Let .about.I, ^.about.I (i) be defined as follows:

^~ I≡{I′⊂I:S(I′)≠empty set}
^~ I(i)≡{I′∈ ^~ I:i∈I}
Specific examples using the above symbols will be described below using Examples 1 and 2. Note that the classification process of classifying a plurality of messages according to a subset of the encoding devices that can access the messages, as illustrated in Examples 1 and 2, may be performed by each encoding device, or an external device may perform the classification process and each encoding device may receive the classification result from the external device.

<Access structure: Example 1>
Example 1 corresponds to Fig. 2. Example 1 is an example of the access structure of a two-input multiple access channel code with a shared message and a two-input interference channel code with a shared message. Let S, I, and A be as follows.

S ≡ {0, 1, 2}
I ≡ {1, 2}
A≡{(0,1), (0,2), (1,1), (2,2)}
As shown in A above, message 0 is shared by encoder 1 and encoder 2, and for each i∈{1,2}, message i is a (private) message that can only be accessed by encoder i. In other words, for each i∈{1,2}, encoder i can access message 0 and message i. This access structure is similar for a two-input interference channel with a shared message. In a multiple access channel code, one decoder decodes all of message 0, message 1, and message 2. In an interference channel code, decoder i decodes message 0 and message i for each i∈{1,2}. From this access structure, the following is obtained from the above definition.

I(0)≡{1,2}
I(1) ≡ {1}
I(2) ≡ {2}
S(1)≡{0,1}
S(2)≡{0,2}
S({1})≡{1}
S({2})≡{2}
S({1,2})≡{0}
^~ I≡{{1,2},{1},{2}}
^~ I(1)≡{{1,2},{1}}
^~ I(2)≡{{1,2},{2}}
Above ^{, ∼} I ≡ {{1,2},{1},{2}} is the set of the subset of coders with a shared message, where the subset of coders with a shared message includes one coder that has access to a message.

^∼ I(1) ≡ {{1, 2}, {1}} is the set of the subset of encoders with shared messages, with respect to encoder 1. ^∼ I(2) ≡ {{1, 2}, {2}} is the set of the subset of encoders with shared messages, with respect to encoder 2.

<Access structure: Example 2>
Example 2 corresponds to Fig. 3. Example 2 is an example of an access structure in a three-input multiple access channel (including an interference channel). Let S, I, and A be as follows.

S≡{1, 3, 12, 23, 123}
I ≡ {1, 2, 3}
A≡{(1,1), (3,3), (12,1), (12,2), (23,2), (23,3), (123,1), (123,2), (123,3)}

For each i∈{1,3}, message i is the private message of encoder i, and for each two-digit number ij∈{12,23}, message ij is the shared message of encoder i and encoder j. Message 123 is the shared message of encoder 1, encoder 2, and encoder 3. In other words, encoder 1 has access to message 1, message 12, and message 123, encoder 2 has access to message 2, message 12, message 23, and message 123, and encoder 3 has access to message 3, message 23, and message 123. Here, partially shared messages 12 and 23 do not appear in the two-input multiple access channel. From this access structure, we obtain the following.

S(1)≡{1,12,123}
S(2)≡{12,23,123}
S(3)≡{3,23,123}
I(1) ≡ {1}
I(3) ≡ {3}
I(12)≡{1,2}
I(23)≡{2,3}
I(123)≡{1,2,3}
S({1})≡{1}
S({3})≡{3}
S({1,2})≡{12}
S({2,3})≡{23}
S({1,2,3})≡{123}
^~ I≡{{1,2,3},{1,2},{2,3},{1},{3}}
^~ I(1)≡{{1,2,3},{1,2},{1}}
^~ I(2)≡{{1,2,3},{1,2},{2,3}}
^~ I(3)≡{{1,2,3},{2,3},{3}}
For a given I′∈ ^∼ I, define S°(I′) as follows, where “S°” is intended to be the letter S with ° at the beginning.

・｛Ｓ（Ｉ′）｝_{Ｉ′∈～Ｉ}はＳの分割（和集合がＳとなる互いに疎な集合族）となる。

・{S(I')} _I'∈～I is a partition of S (a family of sparse sets whose union is S).

If i∈I′, then S(I′)⊂S(i) and S°(I′)⊂S(i) hold, i.e., the encoding device i can access both message sets M _S(I′) ≡{M _s } _s∈S(I′) and M _S°(I′) ≡{M _s } _{s∈S°(I′)} .

・∪ _I'∈~I(i) S(I') = S(i) holds.

Probability distribution

を以下で定義する。

is defined below.

ここで

where

のときは

When

と定義する。

It is defined as:

(Construction of Channel Code)
Next, the configuration of the channel code in this embodiment will be described. The basic idea of the configuration of the channel code in this embodiment is based on reference documents [1] [3] [2] [4]. However, the matters described below are not disclosed in reference documents [1] [3] [2] [4].

For each s∈S, the function

を与える。更に、各ｓ∈Ｓで、

Furthermore, for each s ∈ S,

を与える。ＺＺ^ｎ _ｓが有限体上のｎ次元の線形空間である場合は、具体的なｆ_ｓ，ｇ_ｓとして疎行列を与えることができる。ｃ_ｓ∈ＣＣ_ｓをＣＣ_ｓ上の一様分布に従い発生させたベクトルとする。なお、各ｓで一つのものを適切に選択して固定してもよい。

When ZZ ⁿ _s is an n-dimensional linear space on a finite field, sparse matrices can be given as specific f _s and g _s . Let c _s ∈ CC _s be a vector generated according to a uniform distribution on CC _s . Note that one may be appropriately selected and fixed for each s.

The two sets of functions _fS≡ { _fs } _s∈S , _gS≡ { _gs } _s∈S and the set of vectors _cS≡ { _cs } _s∈S are shared by the encoding device and the decoding device. In other words, the encoding device and the decoding device each hold the above two sets of functions and the set of vectors in a storage unit such as a memory.

For each i∈I, encoder i utilizes fS _(i) , gS _(i) , and cS _(i) . For each j∈J, decoder j utilizes fD _(j) , gD _(j) , and cD _(j) . Furthermore, both encoder and decoder utilize the conditional probability distribution

を利用する。

Use the following.

<Encoding device>
Next, the encoding process by the encoding device of this embodiment will be described. First, a random number generator that satisfies the constraint conditions is provided for the encoding device i. That is, the encoding device i performs a random number generation process that satisfies the constraint conditions using a control unit, which will be described later. The "random number generator" may be called a "random number generation unit."

Given

に対して、

In contrast,

を以下で定義した確率分布に従う確率変数とする。

Let be a random variable that follows the probability distribution defined below.

を満たす任意のｋ，ｋ′∈｛１，２，...，｜^～Ｉ（ｉ）｜｝でｋ＞ｋ′が成立するように、^～Ｉ（ｉ）≡｛Ｉ_ｉ，１，...，Ｉ_{ｉ，｜～Ｉ（ｉ）｜}｝の要素を整列する。ｋ、ｋ´は、^～Ｉ（ｉ）の要素のインデックスである。一例として、^～Ｉ（３）≡｛｛１，２，３｝，｛２，３｝，｛３｝｝は、「数２２」を満たす任意のｋ，ｋ′∈｛１，２，...，｜^～Ｉ（ｉ）｜｝でｋ＞ｋ′が成立している。整列の手順については後述するＡｌｇｏｒｉｔｈｍ ２を用いて説明する。

The elements of ^∼ I(i) ≡ {I i,1 , ..., I i, | ^∼ I(i) | } are sorted so that k >k' holds for any k, k' ∈ { _{1, 2} , ..., _{| ∼ I(i) |} } that satisfies. k and k' are the indices of the elements of ^∼ I(i). As an example, ^∼ I(3) ≡ {{1, 2, 3}, {2, 3}, {3}} holds k >k' for any k, k' ∈ {1, 2, ..., | ^∼ I(i) | } that satisfies "Mathematics 22". The sorting procedure will be explained using Algorithm 2, which will be described later.

The encoding device i generates a random number according to the procedure of Algorithm 1 shown in FIG.

を生成する。この乱数を符号化情報と呼んでもよい。つまり、図４に示すように、入力がなされ、２行目が各ｋで繰り返されることで、出力を得る。整列された^～Ｉ（ｉ）≡｛Ｉ_ｉ，１，...，Ｉ_{ｉ，｜～Ｉ（ｉ）｜}｝が満たしている条件によって、Ａｌｇｏｒｉｔｈｍ １の２行目においては、任意のＩ′に対して

This random number may be called the coded information. That is, as shown in FIG. ₄ , an input is made, and the second line is repeated for each k to obtain an output. In the second line of Algorithm 1, ^for any I′ _,

がすでに得られていることが保証される。

is already obtained.

Given I'∈ ^∼ I, we assume that all encoding devices that have access to the message set m _S(I') (the index belongs to I') can obtain the same output z _S(I') of a random number generator that satisfies the constraints. To satisfy the assumption, for example, each encoding device generates random numbers that satisfy the constraints using a synchronized pseudorandom number sequence (using the same initial value). The function Φ _i :MM _S(i) →XX ⁿ _i executed by encoding device i is defined as follows.

ここで、あるＩ′∈^～Ｉ（ｉ）で

Here, for some I′∈ ^∼ I(i),

を満たしている場合には、符号化装置はエラーを宣言（出力）する。Ｗ_ｉは条件付き確率分布

If _{W i} satisfies the conditional probability distribution

に従う通信路である。ただし、Ｗ_ｉは決定的関数でもよい。

where W _i may be a deterministic function.

Figure 5 shows the data flow related to the encoding process in the encoding device i. This is a diagram that illustrates the process contents described above.

In addition, in the encoding device i in FIG.

を満たさないときはｚ_{Ｓ（Ｉ＿（ｉ，ｋ））}から

If this is not satisfied, then z _{S(I_(i,k))}

への矢印は無い。つまり、

There is no arrow to .

ではｚ_{Ｓ（Ｉ＿（ｉ，ｋ））}を利用しない。

In this case, zS _{(I_(i,k))} is not used.

<Decoding device>
Next, the process in the decryption device j will be described. For each j∈J, the decryption device j generates a random number ^ _zD(j) ≡{^zj, _s } _{s∈D(j) according} to the following distribution from a previously shared vector _cD(j) ≡{ _cs } _s∈D(j) and a communication channel output ^yj∈YYnj , using _a random number generator that satisfies the constraints.

ここでｆ_Ｄ（ｊ）（＾ｚ_Ｄ（ｊ））≡｛ｆ_ｓ（＾ｚ_ｊ，ｓ）｝_{ｓ∈Ｄ（ｊ）}とする。復号装置ｊが実行する関数Ψ_ｊ：ＹＹ^ｎ _ｊ→ＭＭ_Ｄ＿ｊを以下のように定義する。つまり、復号装置ｊは、下記の処理を行うことで入力情報に対する復号を実施して、復号されたメッセージを出力する。

Here, fD _(j) (^ _zD(j) )≡{ _fs (^ _zj,s )} _s∈D(j) . The function _Ψj : ^YYnj → MM _{D_j} executed by the decoding device j is defined as follows. That is, _the decoding device j performs the following process to decode the input information and output the decoded message.

ここで、各ｊ∈Ｊ、ｓ∈Ｄ（ｊ）で＾Ｍ_ｊ，ｓ≡ｇ（＾ｚ_ｊ，ｓ）である。

where ^M _j,s ≡ g(^z _j,s ), for each j ∈ J, s ∈ D(j).

The data flow related to the decoding process in the decoding device j is shown in Fig. 6. This is a diagram equivalent to the diagram illustrating the above-mentioned processing contents. In Fig. 6, D(j) ≡ {sj _,1 , sj _,2 , ..., sj _{, |D(j)|} }.

<Condition that {(r _s , R _s )} _s∈S must satisfy>
For each s∈S, r _s and R _s

とする。

Let us assume that.

In this embodiment, the condition that {(r _s , R _s )} _{s ∈ S} should satisfy will be described. The joint distribution of (Z ⁿ _S , X ⁿ _I , Y ⁿ _J ) is defined by the formula (2):

を用いて以下で与える。

is given below using

｛（Ｒ_ｓ，ｒ_ｓ）｝_ｓ∈Ｓは、Ｉ′∈^～Ｉ，空集合≠Ｓ′⊂Ｓ（Ｉ′），ｊ∈Ｊ，空集合≠Ｄ′⊂Ｄ（ｊ）を満たす任意の（Ｉ′，Ｓ′，ｊ，Ｄ′）で

{(R _s , r _s )} _s∈S is any (I′, S′, j, D′) such that I′∈ ^∼ I, empty set ≠ S′⊂ S(I′), j∈J, empty set ≠ D′⊂ D(j).

を満たしていることを仮定する。ここで

Assume that the following is satisfied:

のときは

When

と定義する。

It is defined as:

Specific

を与えれば、

If we give

が具体的な実数値として求めることができる。このとき、｛Ｒ_ｓ｝_ｓ∈Ｓと｛ｒ_ｓ｝_ｓ∈Ｓに属する変数の一部が実数として与えられたとき、（３）-（５）を満たすように｛Ｒ_ｓ｝_ｓ∈Ｓと｛ｒ_ｓ｝_ｓ∈Ｓの残りの変数を決定するために、線形計画法を用いることができる。このとき、以下の定理が成り立つ。

can be obtained as a specific real value. In this case, when some of the variables belonging to {R _s } _{s ∈ S} and {r _s } _{s ∈ S} are given as real numbers, linear programming can be used to determine the remaining variables of {R _s } _{s ∈ S} and {r _s } _{s ∈ S} so as to satisfy (3)-(5). In this case, the following theorem holds.

Theorem: Let Mj _,s ≡g _s ( ^Znj _,s ). If {( _Rs ,r _s )} _s∈S satisfies (3)-(5), then for any ε>0, if we take n large enough, we can give _fS , _gS , _cS that satisfy (1).

(Spectral entropy rate lower bound and conditional spectral entropy rate upper bound)
Here, detailed definitions of the above-mentioned spectral entropy rate lower limit and conditional spectral entropy rate upper limit will be described.

For a sequence of random variables {U _n } ^∞ _n=1 , the probabilistic upper limit (limit superior in probability) p-limsup _n→∞ U _n and the probabilistic lower limit (limit inferior in probability) p-liminf _n→∞ U _n are defined below.

確率変数列Ｕ≡｛Ｕ_ｎ｝^∞ _ｎ＝１と対応する確率分布列

A sequence of random variables U≡{U _n } ^∞ _n=1 and the corresponding probability distribution sequence

に対して、スペクトルエントロピーレート下限（spectralinf-entropy rate）下バーＨ（Ｕ）を以下で定義する。

For , we define the spectral inf-entropy rate lower bound H(U) as follows:

確率変数列（Ｕ，Ｖ）＝｛（Ｕ_ｎ，Ｖ_ｎ）｝^∞ _ｎ＝１と対応する確率分布列

A sequence of random variables (U, V) = {(U _n , V _n )} ^∞ _{n = 1} and its corresponding probability distribution sequence

に対して、条件付きスペクトルエントロピーレート下限（spectral conditional inf-entropy rate）下バーＨ（Ｕ｜Ｖ）、条件付きスペクトルエントロピーレート上限（spectral conditional sup-entropy rate）上バーＨ（Ｕ｜Ｖ）を各々以下で定義する。

For U|V, the spectral conditional inf-entropy rate lower bound H(U|V) and the spectral conditional sup-entropy rate upper bound H(U|V) are defined as follows:

同時分布μ_ＵＶに従う確率変数Ｕ，Ｖがあるとき、エントロピーＨ（Ｕ）と条件付きエントロピーＨ（Ｕ｜Ｖ）を以下で定義する。

When there are random variables U and V that follow a joint distribution μ _UV , the entropy H(U) and the conditional entropy H(U|V) are defined as follows.

ここで

where

である。

It is.

(Linear extension of partial orderings of subset families)
Here, the above

を満たす任意のｋ，ｋ′∈｛１，２，...，｜^～Ｉ（ｉ）｜｝でｋ＞ｋ′が成立するように、^～Ｉ（ｉ）≡｛Ｉ_ｉ，１，...，Ｉ_{ｉ，｜～Ｉ（ｉ）｜}｝の要素を整列する手順を説明する。なお、ここで説明する手順は、Ｉ，^～Ｉの定義とは無関係に成立する一般的な手順である。Ｉ，^～Ｉへ本手順を適用することは一例である。

We will explain the procedure for sorting the elements of ^∼ I(i) ≡ {I i,1 , ..., I i, | ^∼ I(i) | } so that k >k' holds for any k, k' ∈ { ₁ , 2 _{, ..., | ∼ I(i) |} } that satisfies the above. Note that the procedure explained here is a general procedure that holds regardless of the definitions of I, ^∼ I. Applying this procedure to I, ^∼ I is just one example.

Here, we will explain a method for finding a linear extension of a set of subsets ^∼ I ≡ {I ₁ , ..., I _{| ∼ I |} } (I _k ⊂ I for each k ∈ {1, ..., | ^∼ I | }) that has a partial order based on an inclusion relationship. The method for finding this linear extension is as follows:

を満たす任意のｋ，ｋ′∈｛１，２，...，｜^～Ｉ｜｝でｋ＞ｋ′が成立する集合を求める方法である。

This is a method for finding a set such that k>k' holds for any k, k'∈{1, 2, ..., | ^∼ I|}.

When the partial order is given as a directed acyclic graph (or may be called a directed acyclic graph), the computational complexity is proportional to the sum of | ^∼ I| and the number of directed edges by topological sorting. However, when the partial order is not given as a directed acyclic graph, if the computational complexity required to compare two subsets is assumed to be O(|I|), then the computational complexity required to find the directed acyclic graph is O(|I|| ^∼ I| ² ). In addition, when using the algorithm given in [5], the average computational complexity is O(w|I|| ^∼ I|log| ^∼ I|), assuming that the computational complexity required to compare two subsets is O(|I|). Here, w is the width of the directed acyclic graph.

The alignment procedure proposed in this embodiment is shown in Algorithm 2 in Figure 7. The alignment procedure may be executed by the encoding device or by a device external to the encoding device. When executed by a device external to the encoding device, the result of the execution is received by the encoding device and used in the encoding process.

In our proposed method, we use bucket sort based on the number of elements in a subset. If the computational complexity of finding the number of elements in a subset is O(1), the computational complexity of our proposed method is O(| ^∼ I| + |I|). If the computational complexity of finding the number of elements in a subset is O(I), the computational complexity of our proposed method is O(|I|| ^∼ I|). For example, by using a doubly cyclically linked list as the data structure for ^∼ I and ^∼ L(w), w∈{0,1,...,|I|}, we can reduce the time required for the union operation to O(1).

According to Algorithm 2 shown in Figure 7, an unsorted list is input, and in the first line, ^~ L(v) is initialized for w∈{0, 1, ..., |I|}. In the third line ^{, ~} L(|I'|) ← {I'} ∪ ^~ L(|I'|) is an operation to add I' to ^~ L(|I'|). In other words, it is an operation to put I' into a bucket called " ^~ L(|I'|)" identified by |I'|. By performing this for element I' of each ^~ I, data for the number of elements is set in each "bucket" corresponding to the number of elements.

The 6th line ^～ I ← ^～ L(v) ∪ ^～ I is an operation that adds ^～ L(v) to the beginning of ^～ I. By repeating this process from v = 0 to |I|, data is extracted from the bucket and a sorted subset family is completed.

To reverse either the order or the inclusion relationship, change the sixth line to the operation ^~ I← ^~ I∪ ^~ L(v) ^that adds ^~ L(v) to the end of ~I. Here, the following theorem holds.

Theorem 2: After executing Algorithm 2, for ^∼I≡ {I ₁ ,...,I _|∼I| },

を満たす任意のｋ，ｋ′∈｛１，２，...，｜^～Ｉ｜｝はｋ＞ｋ′を満たしている。

For any k, k′ ∈ {1, 2, ..., | ^≠ I|}, k>k′ satisfies.

When the amount of calculation required to find the number of elements in a subset is O(1), the amount of calculation required to execute a standard sorting algorithm (quick sort, merge sort, heap sort, etc.) using the number of elements ⁱⁿ subset I'∈ ~ I is O(| ^~ I|log| ^~ I|). Therefore, when O(| ^~ I|log| ^~ I|) is smaller than O(|I|) or when I cannot be determined in advance, using a standard sorting algorithm based on the number of elements in the subset results in a smaller amount of calculation.

(others)
As described above, in this embodiment, the use of a random number generator that satisfies the constraints is just an example, and any conversion may be used. In that case, the second line of Algorithm 1 (FIG. 4) showing the processing contents of the encoding device is changed to:

に置き換える。この場合、ｃ_{Ｓ（Ｉ＿（ｉ，ｋ）}）はプリセットされた値なので、これが不要な場合も含む。

In this case, since cS _{(I_(i,k)} ) is a preset value, this also includes cases where this is unnecessary.

(Device configuration example)
FIG. 8 shows the functional configuration of an encoding device 100 and a decoding device 200 that execute the processes described above.

As shown in FIG. 8, the encoding device 100 comprises a transmitting unit 110, a receiving unit 120, a control unit 130, and a memory unit 140, which are connected by a bus. The receiving unit 120 receives a message to be encoded. The control unit 130 executes the encoding process described above. The transmitting unit 110 transmits the encoded information to a communication network. The memory unit 140 stores information necessary for the encoding process.

In the encoding device 100, the information necessary for calculation of the encoding process is stored in advance in the memory unit 140. Dynamically changing information is collected by the receiving unit 120 and stored in the memory unit 140. Alternatively, dynamically changing information is obtained from an external device.

The decoding device 200 comprises a transmitting unit 210, a receiving unit 220, a control unit 230, and a memory unit 240, which are connected by a bus. The receiving unit 220 receives the information to be decoded. The control unit 230 executes the decoding process described above. The transmitting unit 210 transmits the decoded message. The memory unit 240 stores information necessary for the decoding process.

In the decoding device 200, the information necessary for the calculation of the decoding process is stored in advance in the memory unit 240. The receiving unit 220 collects dynamically changing information and stores it in the memory unit 240. Alternatively, the dynamically changing information is obtained from an external device.

The transmitting unit, receiving unit, control unit, and memory unit may also be referred to as a transmitter, receiver, controller (or processor), and memory, respectively.

(Hardware configuration example)
The encoding device 100 and the decoding device 200 may both be realized by a dedicated hardware circuit, or by causing a computer to execute a program. This computer may be a physical computer, or may be a virtual machine on the cloud. Hereinafter, the encoding device 100 and the decoding device 200 will be collectively referred to as the device.

That is, the device can be realized by using hardware resources such as a CPU and memory built into a computer to execute a program corresponding to the processing performed by the device. The program can be recorded on a computer-readable recording medium (such as a portable memory) and stored or distributed. The program can also be provided via a network such as the Internet or email.

Figure 9 is a diagram showing an example of the hardware configuration of the computer. The computer in Figure 9 has a drive device 1000, an auxiliary storage device 1002, a memory device 1003, a CPU 1004, an interface device 1005, a display device 1006, an input device 1007, an output device 1008, etc., which are all connected to each other via a bus B.

The program that realizes the processing on the computer is provided by a recording medium 1001, such as a CD-ROM or a memory card. When the recording medium 1001 storing the program is set in the drive device 1000, the program is installed from the recording medium 1001 via the drive device 1000 into the auxiliary storage device 1002. However, the program does not necessarily have to be installed from the recording medium 1001, but may be downloaded from another computer via a network. The auxiliary storage device 1002 stores the installed program as well as necessary files, data, etc.

When an instruction to start a program is received, the memory device 1003 reads out and stores the program from the auxiliary storage device 1002. The CPU 1004 realizes the functions related to the device in accordance with the program stored in the memory device 1003. The interface device 1005 is used as an interface for connecting to a network. The display device 1006 displays a GUI (Graphical User Interface) based on a program, etc. The input device 1007 is composed of a keyboard and mouse, buttons, a touch panel, etc., and is used to input various operational instructions. The output device 1008 outputs the results of calculations.

(Effects of the embodiment)
The technology according to the present embodiment makes it possible to efficiently encode any access structure in a communication channel having multiple input/output terminals. More specifically, the system configuration can be simplified compared to the conventional technology, and the calculation time can be reduced and the communication efficiency can be improved. In addition, by setting {(r _s , R _s )} _s∈S so as to satisfy the above-mentioned (3)-(5), an error probability close to 0 can be realized.

In addition, as a method of sorting a family of subsets based on their inclusion relationships, sorting can be achieved with a small amount of calculation by sorting based on the number of elements in the subset.

In this embodiment, it is assumed that ^∼ I(i), i∈I are sorted in advance. However, if the message access structure changes dynamically, each encoding device dynamically sorts using the above-mentioned Algorithm 2 or the like.

(Appendix 1)
Regarding the above embodiment, the following supplementary items are further disclosed.
(Additional Note 1)
A coding device in a communication system including a set of coding devices that perform coding in a communication path having a plurality of input/output terminals,
Memory,
at least one processor coupled to the memory;
Including,
The processor,
Receive a message,
A coding device that generates a random number from a message received by the receiving unit based on a classification result obtained by classifying a plurality of messages by a subset of coding devices that can access the messages.
(Additional Note 2)
The encoding device according to claim 1, wherein the processor generates random numbers in an order in which the subsets in a subset family, which is a set of subsets of the encoding devices, are sorted based on an inclusion relationship between the subsets of the encoding devices in the subset family.
(Additional Note 3)
The encoding device according to claim 2, wherein the processor performs the sorting by performing a bucket sort based on the number of elements of each subset in the family of subsets.
(Additional Note 4)
1. An encoding method executed by a computer used as an encoding device in a communication system including a set of encoding devices that perform encoding in a communication path having a plurality of input/output terminals, comprising:
receiving a message;
generating a random number from the received message based on a classification of the plurality of messages by a subset of the encoding devices that have access to the messages;
An encoding method comprising:
(Additional Note 5)
A non-transitory storage medium storing a program executable by a computer used as an encoding device to perform an encoding process,
The encoding process includes:
In a communication system having a set of encoding devices that perform encoding in a communication path having a plurality of input/output terminals,
Receive a message,
A non-transitory storage medium that generates a random number from messages received by the receiver based on a classification result of classifying the plurality of messages by a subset of encoding devices that have access to the messages.

(Appendix 2)
Regarding the above embodiment, the following supplementary items are further disclosed.
(Additional Note 1)
A coding device in a communication system including a set of coding devices that perform coding in a communication path having a plurality of input/output terminals,
Memory,
at least one processor coupled to the memory;
Including,
The processor,
Receive a message,
A coding device that generates code words from messages received by the receiving unit based on a classification result obtained by classifying a plurality of messages by a subset of coding devices that have access to the messages.
(Additional Note 2)
The encoding device according to claim 1, wherein the processor performs the transform in a sorted order of the subsets in a subset family of the encoding devices, based on an inclusion relationship between the subsets of the encoding devices in the subset family, which is a set of the subsets of the encoding devices.
(Additional Note 3)
The encoding device according to claim 2, wherein the processor performs the sorting by performing a bucket sort based on the number of elements of each subset in the family of subsets.
(Additional Note 4)
1. An encoding method executed by a computer used as an encoding device in a communication system including a set of encoding devices that perform encoding in a communication path having a plurality of input/output terminals, comprising:
receiving a message;
generating code words from the received messages based on a classification of the plurality of messages by a subset of the coders that have access to the messages;
An encoding method comprising:
(Additional Note 5)
A non-transitory storage medium storing a program executable by a computer used as an encoding device to perform an encoding process,
The encoding process includes:
In a communication system having a set of coding devices for performing coding in a communication path having a plurality of input/output terminals,
Receive a message,
A non-transitory storage medium for generating code words from messages received by the receiver based on a classification of the plurality of messages by a subset of the coding devices that have access to the messages.

Although the present embodiment has been described above, the present invention is not limited to such a specific embodiment, and various modifications and changes are possible within the scope of the gist of the present invention described in the claims.
[References]
[1] J. Muramatsu, "Channel coding and lossy source coding using a generator of constrained random numbers," IEEE Trans. Inform. Theory, vol. IT-60, no. 5, pp. 2667-2686, May 2014.
[2] J. Muramatsu and S. Miyake, "Channel code using constrained-random-number generator revisited," IEEE Trans. Inform. Theory, vol. IT-65, no. 1, pp. 500-510, Jan. 2019.
[3] J. Muramatsu and S. Miyake, "Multi-terminal codes using constrained-random-number generator," Proceedings of the 2018 International Symposium on Information Theory and its Applications, Singapore, Oct. 28-31, 2018, pp. 612-616. Extended version is available at arXiv:1801.02875v2[cs.IT].
[4] J. Muramatsu, "On the achievability of interference channel coding," https://arxiv.org/abs/2201.10756, 2022.
[5] C. Daskalakis, RM Karp, E. Mossel, S. Riesenfeld, and E. Verbin, "Sorting and selection in posets," https://arxiv.org/abs/0707.1532v1, 2007.

Reference Signs List 100 Encoding device 110 Transmitting unit 120 Receiving unit 130 Control unit 140 Storage unit 200 Decoding device 210 Transmitting unit 220 Receiving unit 230 Control unit 240 Storage unit 1000 Drive device 1001 Recording medium 1002 Auxiliary storage device 1003 Memory device 1004 CPU
1005 Interface device 1006 Display device 1007 Input device 1008 Output device

Claims (5)

A coding device in a communication system including a set of coding devices that perform coding in a communication path having a plurality of input/output terminals,
A receiving unit for receiving a message;
a control unit configured to generate code words from messages received by the receiving unit based on a classification result obtained by classifying a plurality of messages according to a subset of the encoding devices that can access the messages;
An encoding device comprising: The encoding device according to claim 1 , wherein the control unit performs the transformation in an order in which the subsets in a subset family, which is a set of the subsets of the encoding devices, are sorted based on an inclusion relationship between the subsets of the encoding devices in the subset family. The encoding device according to claim 2 , wherein the control unit executes the sorting by performing a bucket sort based on the number of elements of each subset in the family of subsets. 1. An encoding method executed by an encoding device in a communication system including a set of encoding devices that perform encoding in a communication path having a plurality of input/output terminals, comprising:
receiving a message;
generating code words from the received messages based on a classification of the plurality of messages by a subset of the coders that have access to the messages;
An encoding method comprising: A program for causing a computer to function as each part of the encoding device described in any one of claims 1 to 3.

Images