ISSN:
1930-5346
eISSN:
1930-5338
All Issues
Advances in Mathematics of Communications
November 2012 , Volume 6 , Issue 4
Select all articles
Export/Reference:
2012, 6(4): 385-400
doi: 10.3934/amc.2012.6.385
+[Abstract](1137)
+[PDF](413.1KB)
Abstract:
We present two decoding methods (called hybrid and lattice cosets) for affine reflection group codes (ARGC) of any dimension. The algorithms are based on viewing the affine reflection group as a semi-direct product of a crystallographic finite reflection group and its coroot lattice. The proposed lattice cosets method gives an explicit method for drawing a trellis diagram representation of ARGC. The complexities of these two decoding methods, as well as the trade-offs between them, are discussed.
We present two decoding methods (called hybrid and lattice cosets) for affine reflection group codes (ARGC) of any dimension. The algorithms are based on viewing the affine reflection group as a semi-direct product of a crystallographic finite reflection group and its coroot lattice. The proposed lattice cosets method gives an explicit method for drawing a trellis diagram representation of ARGC. The complexities of these two decoding methods, as well as the trade-offs between them, are discussed.
2012, 6(4): 401-418
doi: 10.3934/amc.2012.6.401
+[Abstract](1181)
+[PDF](476.4KB)
Abstract:
Hirzebruch and van der Geer attached theta functions to self-orthogonal, $C\subseteq C^{\bot}$, linear codes $C\subseteq\mathbb F_p^n$, for $p$ an odd prime, and related them to the Lee weight enumerator for the code [5, Ch. 5]. Choie and Jeong extended this result to Jacobi theta functions and provided an analytic proof of the Lee weight MacWilliams Identity for such $C$ [3]. We provide an analytic proof of the Hamming weight MacWilliams Identity for linear codes $C\subseteq\mathbb F_p^n$, generalizing the seminal result for binary codes $C\subseteq\mathbb F_2^n$ [2].
Hirzebruch and van der Geer attached theta functions to self-orthogonal, $C\subseteq C^{\bot}$, linear codes $C\subseteq\mathbb F_p^n$, for $p$ an odd prime, and related them to the Lee weight enumerator for the code [5, Ch. 5]. Choie and Jeong extended this result to Jacobi theta functions and provided an analytic proof of the Lee weight MacWilliams Identity for such $C$ [3]. We provide an analytic proof of the Hamming weight MacWilliams Identity for linear codes $C\subseteq\mathbb F_p^n$, generalizing the seminal result for binary codes $C\subseteq\mathbb F_2^n$ [2].
2012, 6(4): 419-442
doi: 10.3934/amc.2012.6.419
+[Abstract](1167)
+[PDF](491.4KB)
Abstract:
This paper gives a new approach to decoding Hermite codes using the key equation, avoiding the use of majority voting. Our approach corrects up to $(d_{\min}-1)/2$ errors, and works up to some extent also beyond. We present an efficient implementation of our algorithm based on a Sugiyama-type iterative procedure for computing solutions of a key equation.
This paper gives a new approach to decoding Hermite codes using the key equation, avoiding the use of majority voting. Our approach corrects up to $(d_{\min}-1)/2$ errors, and works up to some extent also beyond. We present an efficient implementation of our algorithm based on a Sugiyama-type iterative procedure for computing solutions of a key equation.
2012, 6(4): 443-466
doi: 10.3934/amc.2012.6.443
+[Abstract](1509)
+[PDF](495.4KB)
Abstract:
In this paper we study spread codes: a family of constant-dimension codes for random linear network coding. In other words, the codewords are full-rank matrices of size $k\times n$ with entries in a finite field $\mathbb F_q$. Spread codes are a family of optimal codes with maximal minimum distance. We give a minimum-distance decoding algorithm which requires $\mathcal{O}((n-k)k^3)$ operations over an extension field $\mathbb F_{q^k}$. Our algorithm is more efficient than the previous ones in the literature, when the dimension $k$ of the codewords is small with respect to $n$. The decoding algorithm takes advantage of the algebraic structure of the code, and it uses original results on minors of a matrix and on the factorization of polynomials over finite fields.
In this paper we study spread codes: a family of constant-dimension codes for random linear network coding. In other words, the codewords are full-rank matrices of size $k\times n$ with entries in a finite field $\mathbb F_q$. Spread codes are a family of optimal codes with maximal minimum distance. We give a minimum-distance decoding algorithm which requires $\mathcal{O}((n-k)k^3)$ operations over an extension field $\mathbb F_{q^k}$. Our algorithm is more efficient than the previous ones in the literature, when the dimension $k$ of the codewords is small with respect to $n$. The decoding algorithm takes advantage of the algebraic structure of the code, and it uses original results on minors of a matrix and on the factorization of polynomials over finite fields.
2012, 6(4): 467-478
doi: 10.3934/amc.2012.6.467
+[Abstract](1131)
+[PDF](356.3KB)
Abstract:
Fingerprinting codes are used to prevent dishonest users (traitors) from redistributing digital contents. In this context, codes with the traceability (TA) property and codes with the identifiable parent property (IPP) allow the unambiguous identification of traitors. The existence conditions for IPP codes are less strict than those for TA codes. In contrast, IPP codes do not have an efficient decoding algorithm in the general case. Other codes that have been widely studied but possess weaker identification capabilities are separating codes. It is a well-known result that a TA code is an IPP code, and an IPP code is a separating code. The converse is in general false. However, it has been conjectured that for Reed-Solomon codes all three properties are equivalent. In this paper we investigate this equivalence, providing a positive answer when the number of traitors divides the size of the ground field.
Fingerprinting codes are used to prevent dishonest users (traitors) from redistributing digital contents. In this context, codes with the traceability (TA) property and codes with the identifiable parent property (IPP) allow the unambiguous identification of traitors. The existence conditions for IPP codes are less strict than those for TA codes. In contrast, IPP codes do not have an efficient decoding algorithm in the general case. Other codes that have been widely studied but possess weaker identification capabilities are separating codes. It is a well-known result that a TA code is an IPP code, and an IPP code is a separating code. The converse is in general false. However, it has been conjectured that for Reed-Solomon codes all three properties are equivalent. In this paper we investigate this equivalence, providing a positive answer when the number of traitors divides the size of the ground field.
2012, 6(4): 479-497
doi: 10.3934/amc.2012.6.479
+[Abstract](1540)
+[PDF](373.0KB)
Abstract:
We consider user-private information retrieval (UPIR), an interesting alternative to private information retrieval (PIR) introduced by Domingo-Ferrer et al. In UPIR, the database knows which records have been retrieved, but does not know the identity of the query issuer. The goal of UPIR is to disguise user profiles from the database. Domingo-Ferrer et al. focus on using a peer-to-peer community to construct a UPIR scheme, which we term P2P UPIR. In this paper, we establish a strengthened model for P2P UPIR and clarify the privacy goals of such schemes using standard terminology from the field of privacy research. In particular, we argue that any solution providing privacy against the database should attempt to minimize any corresponding loss of privacy against other users. We give an analysis of existing schemes, including a new attack by the database. Finally, we introduce and analyze two new protocols. Whereas previous work focuses on a special type of combinatorial design known as a configuration, our protocols make use of more general designs. This allows for flexibility in protocol set-up, allowing for a choice between having a dynamic scheme (in which users are permitted to enter and leave the system), or providing increased privacy against other users.
We consider user-private information retrieval (UPIR), an interesting alternative to private information retrieval (PIR) introduced by Domingo-Ferrer et al. In UPIR, the database knows which records have been retrieved, but does not know the identity of the query issuer. The goal of UPIR is to disguise user profiles from the database. Domingo-Ferrer et al. focus on using a peer-to-peer community to construct a UPIR scheme, which we term P2P UPIR. In this paper, we establish a strengthened model for P2P UPIR and clarify the privacy goals of such schemes using standard terminology from the field of privacy research. In particular, we argue that any solution providing privacy against the database should attempt to minimize any corresponding loss of privacy against other users. We give an analysis of existing schemes, including a new attack by the database. Finally, we introduce and analyze two new protocols. Whereas previous work focuses on a special type of combinatorial design known as a configuration, our protocols make use of more general designs. This allows for flexibility in protocol set-up, allowing for a choice between having a dynamic scheme (in which users are permitted to enter and leave the system), or providing increased privacy against other users.
2012, 6(4): 499-503
doi: 10.3934/amc.2012.6.499
+[Abstract](1511)
+[PDF](282.2KB)
Abstract:
It is of interest to know when cyclic self-orthogonal codes of length $n$ over $\mathbb F_q$ do not exist. The conditions, listed by Pless in [7] under which cyclic self-orthogonal codes can not exist, are not always sufficient. An example is given to assert this. Here we give the necessary and sufficient conditions under which cyclic self-orthogonal codes of length $n$ over $\mathbb F_q$ do not exist.
It is of interest to know when cyclic self-orthogonal codes of length $n$ over $\mathbb F_q$ do not exist. The conditions, listed by Pless in [7] under which cyclic self-orthogonal codes can not exist, are not always sufficient. An example is given to assert this. Here we give the necessary and sufficient conditions under which cyclic self-orthogonal codes of length $n$ over $\mathbb F_q$ do not exist.
2012, 6(4): 505-516
doi: 10.3934/amc.2012.6.505
+[Abstract](1218)
+[PDF](396.8KB)
Abstract:
We show how to find $s$-PD-sets of size $s+1$ that satisfy the Gordon-Schönheim bound for partial permutation decoding for the binary simplex codes $\mathcal S_n(\mathbb F_2)$ for all $n \geq 4$, and for all values of $s$ up to $\left\lfloor\frac{2^n-1}{n}\right\rfloor -1$. The construction also applies to the $q$-ary simplex codes $\mathcal S_n(\mathbb F_q)$ for $q>2$, and to $s$-antiblocking information systems of size $s+1$, for $s$ up to $\left\lfloor\frac{(q^n-1)/(q-1)}{n}\right\rfloor -1$ for all $q$.
We show how to find $s$-PD-sets of size $s+1$ that satisfy the Gordon-Schönheim bound for partial permutation decoding for the binary simplex codes $\mathcal S_n(\mathbb F_2)$ for all $n \geq 4$, and for all values of $s$ up to $\left\lfloor\frac{2^n-1}{n}\right\rfloor -1$. The construction also applies to the $q$-ary simplex codes $\mathcal S_n(\mathbb F_q)$ for $q>2$, and to $s$-antiblocking information systems of size $s+1$, for $s$ up to $\left\lfloor\frac{(q^n-1)/(q-1)}{n}\right\rfloor -1$ for all $q$.
2018 Impact Factor: 0.879
Authors
Editors
Referees
Librarians
Email Alert
Add your name and e-mail address to receive news of forthcoming issues of this journal:
[Back to Top]