Fractional repetition (FR) codes is a family of codes for distributed storage systems (DSSs) that allow for uncoded exact repairs having the minimum repair bandwidth. However, in contrast to minimum ...bandwidth regenerating (MBR) codes, where an arbitrary set of a certain size of available nodes is used for a node repair, the repairs with FR codes are table based. This usually allows to store more data compared with MBR codes. In this paper, we consider bounds on the FR capacity, which is the maximum amount of data that can be stored using an FR code. Optimal FR codes which attain these bounds are presented. The constructions of these FR codes are based on combinatorial designs and on families of regular and biregular graphs. These constructions of FR codes for given parameters raise some interesting questions in graph theory. These questions and some of their solutions are discussed in this paper. In addition, based on a connection between FR codes and batch codes, we propose a new family of codes for DSS, namely, FR batch codes, which have the properties of batch codes and FR codes simultaneously. These are the first codes for DSS which allow for uncoded efficient exact repairs and load balancing which can be performed by several users in parallel. Other concepts related to FR codes are also discussed.
Lifted maximum rank distance (MRD) codes, which are constant dimension codes, are considered. It is shown that a lifted MRD code can be represented in such a way that it forms a block design known as ...a transversal design. A slightly different representation of this design makes it similar to a q -analog of a transversal design. The structure of these designs is used to obtain upper bounds on the sizes of constant dimension codes which contain a lifted MRD code. Codes that attain these bounds are constructed. These codes are the largest known constant dimension codes for the given parameters. These transversal designs can also be used to derive a new family of linear codes in the Hamming space. Bounds on the minimum distance and the dimension of such codes are given.
We present a construction for hash-based one-time group signature schemes, and develop a traceable post-quantum multi-time group signature upon it. A group signature scheme allows group members to ...anonymously sign a message on behalf of the entire group. The signatures are unforgeable, and the scheme enables authorized openers to trace the signature back to the original signer when needed. Our construction utilizes three nested layers to build the group signature scheme. The first layer performs the key-management task; it deploys a
transversal design
to assign keys to the group members and the openers, establishing anonymity and providing the construction with traceability. The second layer utilizes sets of hash values,
hash pools
, to build the group public verification key and to connect group members together. The final layer uses a post-quantum hash-based signature scheme, that adds unforgeability to our construction. We extend our scheme to multi-time signatures using Merkle trees and show that this process maintains the scalability property of Merkle-based signatures, while it supports the group members signing any number of messages.
As a general framework, partial geometries play an important role in constructing good low-density parity-check (LDPC) codes with low error-floors. Partial geometries from row–column constrained ...(RC-constrained) arrays of circulant permutation matrices (CPMs) have been determined by Q. Diao et al. In this paper, we study partial geometries from RC-constrained matrices based on group divisible designs (GDDs). From the combinational design perspective, it is shown that the existence of two classes of partial geometries is equivalent to the existence of balanced incomplete block designs (BIBDs) and transversal design (TDs), respectively. Therefore, relevant constructions of BIBDs and TDs are presented. Furthermore, we present a method for constructing LDPC codes with flexible code rate and length parameters by employing the resolvability of GDDs. Numerical results show that the proposed LDPC codes have good performance under iterative decoding over the additive white Gaussian noise (AWGN) channel.
Batch codes, introduced by Ishai, Kushilevitz, Ostrovsky and Sahai, represent the distributed storage of an
n
-element data set on
m
servers in such a way that any batch of
k
data items can be ...retrieved by reading at most one (or more generally,
t
) items from each server, while keeping the total storage over
m
servers equal to
N
. This paper considers a class of batch codes (for
t
=
1
), called combinatorial batch codes (CBCs), where each server stores a subset of a database. A CBC is called optimal if the total storage
N
is minimal for given
n
,
m
, and
k
. A
c
-uniform CBC is a combinatorial batch code where each item is stored in exactly
c
servers. A
c
-uniform CBC is called optimal if its parameter
n
has maximum value for given
m
and
k
. Optimal
c
-uniform CBCs have been known only for
c
∈
{
2
,
k
-
1
,
k
-
2
}
. In this paper we present new constructions of optimal CBCs in both the uniform and general settings, for values of the parameters where tight bounds have not been established previously. In the uniform setting, we provide constructions of two new families of optimal uniform codes with
c
∼
k
. Our constructions are based on affine planes and transversal designs.
Symmetric orthogonal arrays and mixed orthogonal arrays are useful in the design of various experiments. They are also a fundamental tool in the construction of various combinatorial configurations. ...In this paper, we investigated the mixed orthogonal arrays with four and five factors of strength two, and proved that the necessary conditions of such mixed orthogonal arrays are also sufficient with several exceptions and one possible exception.
This letter presents a novel scheme for the design of extended grouping of radio-frequency identification (RFID) tags, based on resolvable transversal designs (RTDs). Extended grouping of RFID tags ...allows identifying missing objects without the requirement for accessing external systems. The original scheme relies on Gallager's parity-check matrices and, as such, it cannot easily achieve designated decoding guarantees due to its pseudo-random nature. In view of the Gallager's parity-check matrix form of incidence matrices of RTDs, this letter proposes extended grouping of RFID tags based on RTDs. The proposed scheme proves to provide designated decoding guarantees more easily than the original scheme. In addition, this letter introduces a simple method, termed group splitting (GS), to improve the performance of extended grouping of RFID tags. Theoretical and simulation results demonstrate that the proposed scheme with or without GS is an efficient approach for the design of extended grouping of RFID tags.
The Existence of a Class of Mixed Orthogonal Arrays PANG, Shanqi; WANG, Yajuan; CHEN, Guangzhou ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
2016, Letnik:
E99.A, Številka:
4
Journal Article
Recenzirano
The orthogonal array is an important object in combinatorial design theory, and it is applied to many fields, such as computer science, coding theory and cryptography etc. This paper mainly studies ...the existence of the mixed orthogonal arrays of strength two with seven factors and presents some new constructions. Consequently, a few new mixed orthogonal arrays are obtained.
On the number of transversal designs Donovan, D.M.; Grannell, M.J.
Journal of combinatorial theory. Series A,
September 2013, 2013-09-00, Letnik:
120, Številka:
7
Journal Article
Recenzirano
Odprti dostop
Bounds are obtained on the number of distinct transversal designs TD(g,n) (having g groups with n points in each group) for certain values of g and n. Amongst other results it is proved that, if ...2<g⩽q+1 where q is a prime power, then the number of nonisomorphic TD(g,qr) designs is at least qαrq2r(1−o(1)) as r→∞, where α=1/q4. The bounds obtained give equivalent bounds for the numbers of distinct and nonisomorphic sets of g−2 mutually orthogonal Latin squares of order n in the corresponding cases. Applications to other combinatorial designs are also described.
This paper gives the answer to a question of R.M. Wilson regarding the existence of group divisible designs of large order. Let
k and
u be positive integers such that
2
⩽
k
⩽
u
. Then there exists an ...integer
m
0
=
m
0
(
k
,
u
)
such that there exists a group divisible design of group type
m
u
with block size
k and index one for any integer
m
⩾
m
0
satisfying the necessary arithmetic conditions
1.
m
(
u
−
1
)
≡
0
mod
(
k
−
1
)
,
2.
m
2
u
(
u
−
1
)
≡
0
mod
k
(
k
−
1
)
.
This paper also presents a large-index asymptotic existence theorem for group divisible
t-designs with a fixed number of groups, fixed group size and fixed block size.
PDF
