Journal of information and communication convergence engineering 2023; 21(4): 300-305
Published online December 31, 2023
https://doi.org/10.56977/jicce.2023.21.4.300
© Korea Institute of Information and Communication Engineering
Correspondence to : Daehwan Kim (E-mail: daehwankim@ulsan.ac.kr)
Department of Electrical, Electronic, and Computer Engineering, University of Ulsan, Ulsan 44610, Republic of Korea
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Audience reactions in response to remote virtual performances must be compressed before being transmitted to the server. The server, which aggregates these data for group insights, requires a distribution code for the transfer. Recently, distributed learning algorithms such as federated learning have gained attention as alternatives that satisfy both the information security and efficiency requirements. In distributed learning, no individual user has access to complete information, and the objective is to achieve a learning effect similar to that achieved with the entire information. It is therefore important to distribute interdependent information among users and subsequently aggregate this information following training. In this paper, we present a new extension technique for minimal code that allows a new minimal code with a different length and Hamming weight to be generated through the product of any vector and a given minimal code. Thus, the proposed technique can generate minimal codes with previously unknown parameters. We also present a scenario wherein these combined methods can be applied.
Keywords Blockchain, Distributed Learning, Federated Learning, VR/AR transmission, Virtual performances
When the reactions of an audience watching a remote virtual performance are to be transmitted to a server, the data must be sufficiently compressed in such a way that it can be easily restored on the server. In such scenarios, the server must aggregate data from remote viewers and learn grouplevel reactions or movements that encompass the whole body, actions, and facial expressions. Furthermore, the transmission of this information requires distribution codes, necessitating distributed coding. Distributed learning algorithms, such as federated learning, have recently gained attention as alternatives that satisfy both information security and efficiency requirements [1,2]. In distributed learning, no individual user has access to complete information, with the objective being to achieve a learning effect similar to that when learning with the entire information. It is therefore important to distribute interdependent information among users and subsequently aggregate this information following training.
Minimal code is a type of linear block code [3] used in various applications such as secret-sharing schemes. In a secret sharing scheme, confidential information is distributed and stored among users so that only a specific authorized subset of users can reconstruct all of it [4].
The distribution of these secrets can be mathematically defined using minimal code. The most important characteristic of such code is that the code word of one user must not be dependent on that of another; i.e., the support of one code word should not be a subset of that of another. Algebraic design methods that satisfy this requirement have previously been proposed [5-8]. Minimal code is expected to become applicable not only in federated learning, but other fields where information dispersion is required, such as blockchain technology. Furthermore, the design of new minimal code techniques is considered an interesting topic in the field of coding theory.
In [5], Aschikhmin and Barg proposed sufficient conditions for a linear block code to be minimal, and presented a method for minimum distance decoding. Mesnager et al. introduced methods for designing minimal codes using characteristic functions defined in finite fields [8]. Various minimal codes have also been designed under the conditions defined by Aschikhmin and Barg [9-11]. Chang and Hyun discovered a design method for minimal codes that is not restricted by sufficient conditions [12]. Ding et al. not only derived the conditions for minimality in binary codes, but also designed a class of infinite binary minimal codes [6]. Heng et al. discovered various binary and ternary minimal codes [13]. Bartoli and Bonini proposed a generalized design method and an inductive extension method for non-binary minimal codes [14]. Most existing minimal codes were designed based on the structures and properties of finite fields, making them limited in length. Instead, it is desirable to design minimal code with new parameters that can accommodate various information lengths and communication environments.
In this paper, we present a new extension technique for block codes for VR/AR transmissions. We briefly examined existing design methods to derive combination methods for new codes. Using our technique, a minimal code with a new length and Hamming weight can be generated through the product of any vector and existing minimal code, thereby yielding minimal codes with previously unknown parameters. We also analyzed the weight properties of the new codes and compared them with those of previously designed codes.
The remainder of this paper is organized as follows. In Section II, we provide an overview of background knowledge pertaining to minimal codes. In Section III, we present a design method based on a combination of distinct minimal codes, and examine properties associated with the weight distribution and minimum distances of the new minimal codes. In Section IV, we introduce scenarios in which the designed minimal codes can be applied, and subsequently present concluding remarks.
A finite field is a type of field that is distinct from a set of real numbers because it consists of a finite elements [15]. Many block codes have been designed over finite fields, as these fields are suitable for basic arithmetic operations. In the following subsections, we introduce the definitions and concepts of finite fields, linear codes, and minimal codes.
A finite field comprises
In the finite field
In this representation, each vector x_{i}, where 0 ≤
According to the properties of linear codes, the sum of two codewords
This support represents a set of coordinates that have nonzero values. The Hamming weight of the codeword
The concept of a minimal code and its application to secret sharing schemes were first proposed by Massey [3]. Ashikhmin and Barg subsequently analyzed the relationship between minimal codes and existing error-correcting codes, obtined the significant properties of minimal codes, such as weight distribution, and explored various aspects related to minimal codes [4]. Furthermore, they derived the sufficient conditions for a linear block code to be minimal, as stated in the following theorem:
Theorem 1 [4]. If a linear block code
where w_{min} and w_{max} are the minimum and maximum support sizes among all codewords in
Although Theorem 1 can serve as an important guideline for designing minimal code, it imposes limitations on the range of Hamming weights among code words, restricting the information capacity to a specific range.
To address this limitation, non-binary minimal codes, as well as binary minimal codes that are not restricted by the conditions of Theorem 1, were proposed by Ding et al. [6]. Furthermore, Mesnager et al. introduced integrated approaches for designing minimal codes, encompassing both binary and non-binary codes that fall outside the scope of Theorem 1 [8]. In this context, codes with an alphabet size of two are referred to as binary, whereas those with a larger alphabet are referred to as non-binary. The design of binary and nonbinary distribution codes is an important topic, as although the design schemes are similar, their applications are considerably different.
For 0 ≤
Theorem 2. Let us define codeword
where 0≤
Proof: First, we prove that
becomes
Furthermore,
for some
and there exists 0 ≤
Therefore, the support of codeword is
In Theorem 2, each codeword
The weight distribution of the new code
In linear codes, the minimum distance – which represents the distance between code words – is an important performance metric associated with error probability. Owing to linearity, the minimum distance is equal to the minimum Hamming weight among the code words [3]. Assuming that the original minimum distance of the minimal code
Table 1 . Sample new parameters of minimal codes (
N | K | d | Number of distinct weights | |
---|---|---|---|---|
Original Codes | 511 | 10 | 120 | 3 |
Extended Codes | 5110 | 10 | 120~1200 | 3~30 |
Let us define the extended length
where
Here,
Our code construction is based on the interleaving of two different minimal codes, with the indices of a new code determined by a combination of the two codes. Consider a minimal code
where ⊙ is the binary AND operator, 0 ≤
The codewords of
The newly designed code is fundamentally determined by the weight distribution of the original code. However, by altering the combinations of the constituent codes, new weight distributions can be generated, as discussed in III.B.1. Table 2 presents the experimentally obtained weight distributions for each combination.
Table 2 . Weight distributions of a sample original code and its extension
Code | Lengths | No. of Possible Weights |
---|---|---|
Original | 255 | 6 |
Extended | 510 | 12 |
As seen from the table, codes with a wider range of weight distributions can be synthesized by combining existing codes. This enables a greater variety of information combinations, increasing the diversity of dispersed information.
The newly designed code from III.B.1 can be utilized to combine information from two distributed learning systems into a single entity. The dispersed forms of information from each system can be incorporated into existing code words without modification. Moreover, because the new codewords remain mutually independent, confidentiality is maintained in a dispersed formIf the codes with relatively prime lengths presented in III.B.2 are not used, finding a method to combine data from the two systems becomes an additional challenge.
In this study, we propose a method that extends minimal codes to an arbitrary multiple length by increasing the Hamming weight. Furthermore, we demonstrated an increase in the minimum distance of the code; thus, a new Hamming weight distribution can be generated through various combinations. Our extension method can be applied to codes with new designs that can accommodate various parameters.
This research was supported by the Culture, Sports, and Tourism R&D Program through a Korea Creative Content Agency grant, funded by the Ministry of Culture, Sports, and Tourism in 2023. (Project name: Development of Virtual Reality Performance Platform Supporting Multiuser Participation and Real-Time Interaction, Project Number: R2021040046)
She is currently pursuing a Bachelor’s degree in AI convergence at the University of Ulsan. Her research interests include graph representation learning, biomedical engineering with deep learning, and security.
She is currently pursuing a Bachelor’s degree in AI convergence at the University of Ulsan. Her research interests include machine learning for communication, graph machine learning, and coding theory.
He received B.S., M.S., and Ph.D. degrees in electronics and electrical engineering from the Pohang University of Science and Technology (POSTECH), Pohang, Korea, in 2005, 2007, and 2011, respectively. He was a postdoctoral researcher in Communications and Signal Design Laboratory, Department of Electrical Engineering, POSTECH from March 2011 to February 2013. He was an Assistant Professor at the School of Electrical and Computer Engineering of the Ulsan National Institute of Science and Technology from February 2013 to February 2021. He is currently working as an Associate Professor at the School of Electronic, Electrical, and Computer Engineering at the University of Ulsan. His research interests include information theory for machine learning, physical layer security, and coding theory.
He completed his Ph.D. in computer science and engineering at the Pohang University of Science and Technology in 2011. He is currently a professor at the School of IT Convergence at the University of Ulsan. His main research interests include computer vision, AI, deep learning, and VR/AR.
He completed a B.S. degree (1996) in Electronics Engineering at Inha University, an M.S.E. (1998) in Information and Communications Engineering at GIST, and a Ph.D. (2014) in Computer Science at the Korea Advance Institute of Science and Technology (KAIST), Korea. He joined the Electronics and Telecommunications Research Institute (ETRI) in 1998 and has been working as a principal researcher of the Virtual Reality Research Team since then. His research interests include virtual reality, haptics, and human-computer interaction.
Journal of information and communication convergence engineering 2023; 21(4): 300-305
Published online December 31, 2023 https://doi.org/10.56977/jicce.2023.21.4.300
Copyright © Korea Institute of Information and Communication Engineering.
Seo-Hee Hwang ^{1}, Si-Yeon Pak ^{1}, Jin-Ho Chung ^{2}, Daehwan Kim ^{2*}, and Yongwan Kim^{3 }, Member, KIICE
^{1}Department of AI Convergence, University of Ulsan, Ulsan 44610, Republic of Korea
^{2}Department of Electrical, Electronic, and Computer Engineering, University of Ulsan, Ulsan 44610, Republic of Korea
^{3}VR/AR Content Research Section, Communications & Media Research Laboratory, Electronics and Telecommunications Research Institute (ETRI), Daejeon 34129, Republic of Korea
Correspondence to:Daehwan Kim (E-mail: daehwankim@ulsan.ac.kr)
Department of Electrical, Electronic, and Computer Engineering, University of Ulsan, Ulsan 44610, Republic of Korea
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Audience reactions in response to remote virtual performances must be compressed before being transmitted to the server. The server, which aggregates these data for group insights, requires a distribution code for the transfer. Recently, distributed learning algorithms such as federated learning have gained attention as alternatives that satisfy both the information security and efficiency requirements. In distributed learning, no individual user has access to complete information, and the objective is to achieve a learning effect similar to that achieved with the entire information. It is therefore important to distribute interdependent information among users and subsequently aggregate this information following training. In this paper, we present a new extension technique for minimal code that allows a new minimal code with a different length and Hamming weight to be generated through the product of any vector and a given minimal code. Thus, the proposed technique can generate minimal codes with previously unknown parameters. We also present a scenario wherein these combined methods can be applied.
Keywords: Blockchain, Distributed Learning, Federated Learning, VR/AR transmission, Virtual performances
When the reactions of an audience watching a remote virtual performance are to be transmitted to a server, the data must be sufficiently compressed in such a way that it can be easily restored on the server. In such scenarios, the server must aggregate data from remote viewers and learn grouplevel reactions or movements that encompass the whole body, actions, and facial expressions. Furthermore, the transmission of this information requires distribution codes, necessitating distributed coding. Distributed learning algorithms, such as federated learning, have recently gained attention as alternatives that satisfy both information security and efficiency requirements [1,2]. In distributed learning, no individual user has access to complete information, with the objective being to achieve a learning effect similar to that when learning with the entire information. It is therefore important to distribute interdependent information among users and subsequently aggregate this information following training.
Minimal code is a type of linear block code [3] used in various applications such as secret-sharing schemes. In a secret sharing scheme, confidential information is distributed and stored among users so that only a specific authorized subset of users can reconstruct all of it [4].
The distribution of these secrets can be mathematically defined using minimal code. The most important characteristic of such code is that the code word of one user must not be dependent on that of another; i.e., the support of one code word should not be a subset of that of another. Algebraic design methods that satisfy this requirement have previously been proposed [5-8]. Minimal code is expected to become applicable not only in federated learning, but other fields where information dispersion is required, such as blockchain technology. Furthermore, the design of new minimal code techniques is considered an interesting topic in the field of coding theory.
In [5], Aschikhmin and Barg proposed sufficient conditions for a linear block code to be minimal, and presented a method for minimum distance decoding. Mesnager et al. introduced methods for designing minimal codes using characteristic functions defined in finite fields [8]. Various minimal codes have also been designed under the conditions defined by Aschikhmin and Barg [9-11]. Chang and Hyun discovered a design method for minimal codes that is not restricted by sufficient conditions [12]. Ding et al. not only derived the conditions for minimality in binary codes, but also designed a class of infinite binary minimal codes [6]. Heng et al. discovered various binary and ternary minimal codes [13]. Bartoli and Bonini proposed a generalized design method and an inductive extension method for non-binary minimal codes [14]. Most existing minimal codes were designed based on the structures and properties of finite fields, making them limited in length. Instead, it is desirable to design minimal code with new parameters that can accommodate various information lengths and communication environments.
In this paper, we present a new extension technique for block codes for VR/AR transmissions. We briefly examined existing design methods to derive combination methods for new codes. Using our technique, a minimal code with a new length and Hamming weight can be generated through the product of any vector and existing minimal code, thereby yielding minimal codes with previously unknown parameters. We also analyzed the weight properties of the new codes and compared them with those of previously designed codes.
The remainder of this paper is organized as follows. In Section II, we provide an overview of background knowledge pertaining to minimal codes. In Section III, we present a design method based on a combination of distinct minimal codes, and examine properties associated with the weight distribution and minimum distances of the new minimal codes. In Section IV, we introduce scenarios in which the designed minimal codes can be applied, and subsequently present concluding remarks.
A finite field is a type of field that is distinct from a set of real numbers because it consists of a finite elements [15]. Many block codes have been designed over finite fields, as these fields are suitable for basic arithmetic operations. In the following subsections, we introduce the definitions and concepts of finite fields, linear codes, and minimal codes.
A finite field comprises
In the finite field
In this representation, each vector x_{i}, where 0 ≤
According to the properties of linear codes, the sum of two codewords
This support represents a set of coordinates that have nonzero values. The Hamming weight of the codeword
The concept of a minimal code and its application to secret sharing schemes were first proposed by Massey [3]. Ashikhmin and Barg subsequently analyzed the relationship between minimal codes and existing error-correcting codes, obtined the significant properties of minimal codes, such as weight distribution, and explored various aspects related to minimal codes [4]. Furthermore, they derived the sufficient conditions for a linear block code to be minimal, as stated in the following theorem:
Theorem 1 [4]. If a linear block code
where w_{min} and w_{max} are the minimum and maximum support sizes among all codewords in
Although Theorem 1 can serve as an important guideline for designing minimal code, it imposes limitations on the range of Hamming weights among code words, restricting the information capacity to a specific range.
To address this limitation, non-binary minimal codes, as well as binary minimal codes that are not restricted by the conditions of Theorem 1, were proposed by Ding et al. [6]. Furthermore, Mesnager et al. introduced integrated approaches for designing minimal codes, encompassing both binary and non-binary codes that fall outside the scope of Theorem 1 [8]. In this context, codes with an alphabet size of two are referred to as binary, whereas those with a larger alphabet are referred to as non-binary. The design of binary and nonbinary distribution codes is an important topic, as although the design schemes are similar, their applications are considerably different.
For 0 ≤
Theorem 2. Let us define codeword
where 0≤
Proof: First, we prove that
becomes
Furthermore,
for some
and there exists 0 ≤
Therefore, the support of codeword is
In Theorem 2, each codeword
The weight distribution of the new code
In linear codes, the minimum distance – which represents the distance between code words – is an important performance metric associated with error probability. Owing to linearity, the minimum distance is equal to the minimum Hamming weight among the code words [3]. Assuming that the original minimum distance of the minimal code
Table 1 . Sample new parameters of minimal codes (
N | K | d | Number of distinct weights | |
---|---|---|---|---|
Original Codes | 511 | 10 | 120 | 3 |
Extended Codes | 5110 | 10 | 120~1200 | 3~30 |
Let us define the extended length
where
Here,
Our code construction is based on the interleaving of two different minimal codes, with the indices of a new code determined by a combination of the two codes. Consider a minimal code
where ⊙ is the binary AND operator, 0 ≤
The codewords of
The newly designed code is fundamentally determined by the weight distribution of the original code. However, by altering the combinations of the constituent codes, new weight distributions can be generated, as discussed in III.B.1. Table 2 presents the experimentally obtained weight distributions for each combination.
Table 2 . Weight distributions of a sample original code and its extension.
Code | Lengths | No. of Possible Weights |
---|---|---|
Original | 255 | 6 |
Extended | 510 | 12 |
As seen from the table, codes with a wider range of weight distributions can be synthesized by combining existing codes. This enables a greater variety of information combinations, increasing the diversity of dispersed information.
The newly designed code from III.B.1 can be utilized to combine information from two distributed learning systems into a single entity. The dispersed forms of information from each system can be incorporated into existing code words without modification. Moreover, because the new codewords remain mutually independent, confidentiality is maintained in a dispersed formIf the codes with relatively prime lengths presented in III.B.2 are not used, finding a method to combine data from the two systems becomes an additional challenge.
In this study, we propose a method that extends minimal codes to an arbitrary multiple length by increasing the Hamming weight. Furthermore, we demonstrated an increase in the minimum distance of the code; thus, a new Hamming weight distribution can be generated through various combinations. Our extension method can be applied to codes with new designs that can accommodate various parameters.
This research was supported by the Culture, Sports, and Tourism R&D Program through a Korea Creative Content Agency grant, funded by the Ministry of Culture, Sports, and Tourism in 2023. (Project name: Development of Virtual Reality Performance Platform Supporting Multiuser Participation and Real-Time Interaction, Project Number: R2021040046)
Table 1 . Sample new parameters of minimal codes (
N | K | d | Number of distinct weights | |
---|---|---|---|---|
Original Codes | 511 | 10 | 120 | 3 |
Extended Codes | 5110 | 10 | 120~1200 | 3~30 |
Table 2 . Weight distributions of a sample original code and its extension.
Code | Lengths | No. of Possible Weights |
---|---|---|
Original | 255 | 6 |
Extended | 510 | 12 |
Jeongkyu Hong*, Member, KIICE
Journal of information and communication convergence engineering 2024; 22(1): 64-69 https://doi.org/10.56977/jicce.2024.22.1.64Gi-Beom Song and Man-Hee Lee
Journal of information and communication convergence engineering 2018; 16(4): 235-241 https://doi.org/10.6109/jicce.2018.16.4.235Anik Islam, Md Fazlul Kader, Soo Young Shin
Journal of information and communication convergence engineering 2019; 17(3): 174-184 https://doi.org/10.6109/jicce.2019.17.3.174