
Binary AIFV codes are lossless codes that generalize the class of
instantaneous FV codes. The code uses two code trees and assigns source symbols
to incomplete internal nodes as well as to leaves. AIFV codes are empirically
shown to attain better compression ratio than Huffman codes. Nevertheless, an
upper bound on the redundancy of optimal binary AIFV codes is only known to be
1, which is the same as the bound of Huffman codes. In this paper, the upper
bound is improved to 1/2, which is shown to coincide with the worstcase
redundancy of the codes. Along with this, the worstcase redundancy is derived
in terms of $p_{\max}\geq$1/2, where $p_{\max}$ is the probability of the most
likely source symbol. Additionally, we propose an extension of binary AIFV
codes, which use $m$ code trees and allow at most $m$bit decoding delay. We
show that the worstcase redundancy of the extended binary AIFV codes is $1/m$
for $m \leq 4.$

The 10th AsiaEurope workshop in "Concepts in Information Theory and
Communications" AEW10 was held in Boppard, Germany on June 2123, 2017. It is
based on a longstanding cooperation between Asian and European scientists. The
first workshop was held in Eindhoven, the Netherlands in 1989. The idea of the
workshop is threefold: 1) to improve the communication between the scientist in
the different parts of the world; 2) to exchange knowledge and ideas; and 3) to
pay a tribute to a well respected and special scientist.

In communication through asymmetric channels the capacityachieving input
distribution is not uniform in general. Homophonic coding is a framework to
invertibly convert a (usually uniform) message into a sequence with some target
distribution, and is a promising candidate to generate codewords with the
nonuniform target distribution for asymmetric channels. In particular, a
VariabletoFixed length (VF) homophonic code can be used as a suitable
component for channel codes to avoid decoding error propagation. However, the
existing VF homophonic code requires the knowledge of the maximum relative gap
of probabilities between two adjacent sequences beforehand, which is an
unrealistic assumption for long block codes. In this paper we propose a new VF
homophonic code without such a requirement by allowing onesymbol decoding
delay. We evaluate this code theoretically and experimentally to verify its
asymptotic optimality.

In this paper, the posterior matching scheme proposed by Shayevits and Feder
is extended to the Gaussian broadcast channel with feedback, and the error
probabilities and achievable rate region are derived for this coding strategy
by using the iterated random function theory. A variant of the OzarowLeung
code for the general twouser broadcast channel with feedback can be realized
as a special case of our coding scheme. Furthermore, for the symmetric Gaussian
broadcast channel with feedback, our coding scheme achieves the linearfeedback
sumcapacity like the LQG code and outperforms the Kramer code.

Homophonic coding is a framework to reversibly convert a message into a
sequence with some target distribution. This is a promising tool to generate a
codeword with a biased codesymbol distribution, which is required for
capacityachieving communication by asymmetric channels. It is known that
asymptotically optimal homophonic coding can be realized by a FixedtoVariable
(FV) length code using an interval algorithm similar to a random number
generator. However, FV codes are not preferable as a component of channel codes
since a decoding error propagates to all subsequent codewords. As a solution
for this problem an asymptotically optimal VariabletoFixed (VF) length
homophonic code, dual ShannonFanoEliasGray (dual SFEG) code, is proposed in
this paper. This code can be interpreted as a dual of a modified
ShannonFanoElias (SFE) code based on Gray code. It is also shown as a
byproduct that the modified SFE code, named SFEG code, achieves a better
coding rate than the original SFE code in lossless source coding.

We propose almost instantaneous fixedtovariablelength (AIFV) codes such
that two (resp. $K1$) code trees are used if code symbols are binary (resp.
$K$ary for $K \geq 3$), and source symbols are assigned to incomplete internal
nodes in addition to leaves. Although the AIFV codes are not instantaneous
codes, they are devised such that the decoding delay is at most two bits (resp.
one code symbol) in the case of binary (resp. $K$ary) code alphabet. The AIFV
code can attain better average compression rate than the Huffman code at the
expenses of a little decoding delay and a little large memory size to store
multiple code trees. We also show for the binary and ternary AIFV codes that
the optimal AIFV code can be obtained by solving 01 integer programming
problems.

In this paper, we propose a new coding scheme for symmetric Gaussian
interference channels with feedback based on the ideas of timevarying coding
schemes. The proposed scheme improves the SuhTse and Kramer inner bounds of
the channel capacity for the cases of weak and not very strong interference.
This improvement is more significant when the signaltonoise ratio (SNR) is
not very high. It is shown theoretically and numerically that our coding scheme
can outperform the Kramer code. In addition, the generalized degreesoffreedom
of our proposed coding scheme is equal to the SuhTse scheme in the strong
interference case. The numerical results show that our coding scheme can attain
better performance than the SuhTse coding scheme for all channel parameters.
Furthermore, the simplicity of the encoding/decoding algorithms is another
strong point of our proposed coding scheme compared with the SuhTse coding
scheme. More importantly, our results show that an optimal coding scheme for
the symmetric Gaussian interference channels with feedback can be achieved by
using only marginal posterior distributions under a better cooperation strategy
between transmitters.

For information transmission a discrete time channel with independent
additive Gaussian noise is used. There is also another channel with independent
additive Gaussian noise (the feedback channel), and the transmitter observes
without delay all outputs of the forward channel via that channel. Transmission
of nonexponential number of messages is considered (i.e. transmission rate
equals zero) and the achievable decoding error exponent for such a combination
of channels is investigated. The transmission method strengthens the method
used by authors earlier for BSC and Gaussian channels. In particular, for small
feedback noise, it allows to gain 33.3\% (instead of 23.6\% earlier in the
similar case of Gaussian channel).

Private information retrieval scheme for coded data storage is considered in
this paper. We focus on the case where the size of each data record is large
and hence only the download cost (but not the upload cost for transmitting
retrieval queries) is of interest. We prove that the tradeoff between storage
cost and retrieval/download cost depends on the number of data records in the
system. We also propose a fairly general class of linear storage codes and
retrieval schemes and derive conditions under which our retrieval schemes are
errorfree and private. Tradeoffs between the storage cost and retrieval costs
are also obtained. Finally, we consider special cases when the underlying
storage code is based on an MDS code. Using our proposed method, we show that a
randomly generated retrieval scheme is indeed very likely to be private and
errorfree.

In the case of ordinary identification coding, a code is devised to identify
a single object among $N$ objects. But, in this paper, we consider an
identification coding problem to identify $K$ objects at once among $N$ objects
in the both cases that $K$ objects are ranked or not ranked. By combining
KurosawaYoshida scheme with MoulinKoetter scheme, an efficient identification
coding scheme is proposed, which can attain high coding rate and error
exponents compared with the case that an ordinary identification code is used
$K$ times. Furthermore, the achievable triplet of rate and error exponents of
type I and type II decoding error probabilities are derived for the proposed
coding scheme.

In this paper, we discuss coding theorems on a $(2, 2)$threshold scheme in
the presence of an opponent who impersonates one of the two shareholders in an
asymptotic setup. We consider a situation where $n$ secrets $S^n$ from a
memoryless source is blockwisely encoded to two shares and the two shares are
decoded to $S^n$ with permitting negligible decoding error. We introduce
correlation level of the two shares and characterize the minimum attainable
rates of the shares and a uniform random number for realizing a $(2,
2)$threshold scheme that is secure against the impersonation attack by an
opponent. It is shown that, if the correlation level between the two shares
equals to an $\ell \ge 0$, the minimum attainable rates coincide with
$H(S)+\ell$, where $H(S)$ denotes the entropy of the source, and the maximum
attainable exponent of the success probability of the impersonation attack
equals to $\ell$. We also give a simple construction of an encoder and a
decoder using an ordinary $(2,2)$threshold scheme where the two shares are
correlated and attains all the bounds.

For the information transmission a binary symmetric channel is used. There is
also another noisy binary symmetric channel (feedback channel), and the
transmitter observes without delay all the outputs of the forward channel via
that feedback channel. The transmission of a nonexponential number of messages
(i.e. the transmission rate equals zero) is considered. The achievable decoding
error exponent for such a combination of channels is investigated. It is shown
that if the crossover probability of the feedback channel is less than a
certain positive value, then the achievable error exponent is better than the
similar error exponent of the nofeedback channel.
The transmission method described and the corresponding lower bound for the
error exponent can be strengthened, and also extended to the positive
transmission rates.

It is known that a message can be transmitted safely against any wiretapper
via a noisy channel without a secret key if the coding rate is less than the
socalled secrecy capacity $C_S$, which is usually smaller than the channel
capacity $C$. In order to remove the loss $C  C_S$, we propose a multiplex
coding scheme with plural independent messages. In this paper, it is shown that
the proposed multiplex coding scheme can attain the channel capacity as the
total rate of the plural messages and the perfect secrecy for each message. The
coding theorem is proved by extending Hayashi's proof, in which the coding of
the channel resolvability is applied to wiretap channels.

In key management schemes that realize secure multicast communications
encrypted by group keys on a public network, tree structures are often used to
update the group keys efficiently. Selcuk and Sidhu have proposed an efficient
scheme which updates dynamically the tree structures based on the withdrawal
probabilities of members. In this paper, it is shown that SelcukSidhu scheme
is asymptotically optimal for the cost of withdrawal. Furthermore, a new key
management scheme, which takes account of key update costs of joining in
addition to withdrawal, is proposed. It is proved that the proposed scheme is
also asymptotically optimal, and it is shown by simulation that it can attain
good performance for nonasymptotic cases.

It is known that for any general access structure, a secret sharing scheme
(SSS) can be constructed from an (m,m)threshold scheme by using the socalled
cumulative map or from a (t,m)threshold SSS by a modified cumulative map.
However, such constructed SSSs are not efficient generally. In this paper, we
propose a new method to construct a SSS from a $(t,m)$threshold scheme for any
given general access structure. In the proposed method, integer programming is
used to distribute optimally the shares of (t,m)threshold scheme to each
participant of the general access structure. From the optimality, it can always
attain lower coding rate than the cumulative maps except the cases that they
give the optimal distribution. The same method is also applied to construct
SSSs for incomplete access structures and/or ramp access structures.

Ramp secret sharing (SS) schemes can be classified into strong ramp SS
schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out
any part of a secret explicitly even in the case where some information about
the secret leaks from a nonqualified set of shares, and hence, they are more
desirable than weak ramp SS schemes. However, it is not known how to construct
the strong ramp SS schemes in the case of general access structures. In this
paper, it is shown that a strong ramp SS scheme can always be constructed from
a SS scheme with plural secrets for any feasible general access structure. As a
byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's
polynomial interpolation method are {\em not} always strong.

Quantum secret sharing schemes encrypting a quantum state into a multipartite
entangled state are treated. The lower bound on the dimension of each share
given by Gottesman [Phys. Rev. A \textbf{61}, 042311 (2000)] is revisited based
on a relation between the reversibility of quantum operations and the Holevo
information. We also propose a threshold ramp quantum secret sharing scheme and
evaluate its coding efficiency.