
-
Previous Article
Optimal antiblocking systems of information sets for the binary codes related to triangular graphs
- AMC Home
- This Issue
-
Next Article
Involutory-Multiple-Lightweight MDS Matrices based on Cauchy-type Matrices
New optimal error-correcting codes for crosstalk avoidance in on-chip data buses
School of Mathematical Sciences, University of Science and Technology of China, Wu Wen-Tsun Key Laboratory of Mathematics, No. 96 Jinzhai Road, Hefei, 230026, Anhui, China |
Codes that simultaneously provide for low power dissipation, cross-talk avoidance, and error correction in the ultra deep submicron/nanometer VLSI fabrication, were recently introduced by Chee et al. in 2015. Such codes were revealed to be closely related to balanced sampling plans avoiding adjacent units, which are widely used in the statistical design of experiments. In this paper, we construct a new family of optimal codes with such properties, by determining the maximum size of packing sampling plans avoiding certain units.
References:
[1] |
D. Bertozzi, L. Benini and G. D. Micheli, Low power error resilient encoding for on-chip data buses, Proceedings of the Conference on Design, Automation and Test in Europe, IEEE Computer Society, (2002), 102–109.
doi: 10.1109/DATE.2002.998256. |
[2] |
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976. |
[3] |
D. Bryant, Y. X. Chang, C. A. Rodger and R. Wei,
Two-dimensional balanced sampling plans excluding contiguous units, Communications in Statistics-Theory and Methods, 31 (2002), 1441-1455.
doi: 10.1081/STA-120006078. |
[4] |
Y. M. Chee, C. J. Colbourn and A. C. H. Ling, Optimal memoryless encoding for low power off-chip data buses, 2006 IEEE/ACM International Conference on Computer Aided Design, IEEE, (2006), 369–374.
doi: 10.1145/1233501.1233575. |
[5] |
Y. M. Chee, C. J. Colbourn, A. C. H. Ling, H. Zhang and X. D. Zhang,
Optimal low-power coding for error correction and crosstalk avoidance in on-chip data buses, Des. Codes Cryptogr., 77 (2015), 479-491.
doi: 10.1007/s10623-015-0084-4. |
[6] |
C. J. Colbourn and A. C. H. Ling,
A class of partial triple systems with applications in survey sampling, Communications in Statistics-Theory and Methods, 27 (1998), 1009-1018.
doi: 10.1080/03610929808832141. |
[7] |
C. J. Colbourn and A. C. H. Ling, Balanced sampling plans with block size four excluding
contiguous units, Australasian Journal of Combinatorics, 20 (1999), 37-46.
doi: ajc.maths.uq.edu.au. |
[8] |
C. J. Duan, A. Tirumala and S. P. Khatri, Analysis and avoidance of cross-talk in on-chip buses, HOT 9 Interconnects Symposium on High Performance Interconnects, IEEE, (2001), 133–138.
doi: 10.1109/HIS.2001.946705. |
[9] |
M. Favalli and C. Metra,
Bus crosstalk fault-detection capabilities of error-detecting codes for on-line testing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7 (1999), 392-396.
doi: 10.1109/92.784100. |
[10] |
A. S. Hedayat, C. R. Rao and J. Stufken,
Sampling plans excluding contiguous units, Sampling, Handbook of Statist., North-Holland, Amsterdam, 6 (1988), 575-583.
doi: 10.1016/0378-3758(88)90070-5. |
[11] |
A. Hedayat, C. Rao and J. Stufken,
24 Designs in survey sampling avoiding contiguous units, Handbook of Statistics, 6 (1988), 575-583.
doi: 10.1016/S0169-7161(88)06026-2. |
[12] |
I. Iqbal, M. H. Tahir, M. Akhtar, S. S. A. Ghazali, J. Shabbir and N. S. Bukhari,
Generalized polygonal designs with block size 3 and $\lambda = 1$, Journal of Statistical Planning and Inference, 139 (2009), 3200-3219.
doi: 10.1016/j.jspi.2009.02.018. |
[13] |
Z. Khan, T. Arslan and A. T. Erdogan, A dual low power and crosstalk immune encoding scheme for system-on-chip buses, International Workshop on Power and Timing Modeling, Optimization and Simulation, (2004), 585–592.
doi: 10.1007/978-3-540-30205-6_60. |
[14] |
H. R. Kong, J. G. Lei and Y. Zhang,
On constructions for two dimensional balanced sampling plan excluding contiguous units with block size four, Discrete Mathematics, 308 (2008), 3729-3743.
doi: 10.1016/j.disc.2007.07.065. |
[15] |
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. |
[16] |
Y. Miao and L. Zhu,
Existence of incomplete group divisible designs, J. Comb. Math. Comb. Comput., 6 (1989), 33-49.
|
[17] |
K. N. Patel and I. L. Markov, Error-correction and crosstalk avoidance in DSM busses, Proceedings of the 2003 International Workshop on System-level Interconnect Prediction, ACM, (2003), 9–14.
doi: 10.1145/639929.639933. |
[18] |
S. Ramprasad, N. R. Shanbhag and I. N. Hajj,
A coding framework for low-power address and data busses, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7 (1999), 212-221.
doi: 10.1109/92.766748. |
[19] |
D. Rossi, V. E. S. van Dijk, R. P. Kleihorst, A. H. Nieuwland and C. Metra, Coding scheme for low energy consumption fault-tolerant bus, Proceedings of the Eighth IEEE International On-Line Testing Workshop (IOLTW), IEEE, (2002), 8–12.
doi: 10.1109/OLT.2002.1030176. |
[20] |
J. E. Simpson,
Langford sequences: Perfect and hooked, Discrete Mathematics, 44 (1983), 97-104.
doi: 10.1016/0012-365X(83)90008-0. |
[21] |
M. R. Stan and W. P. Burleson,
Bus-invert coding for low-power I/O, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 3 (1995), 49-58.
doi: 10.1109/92.365453. |
[22] |
J. Stufken,
Combinatorial and statistical aspects of sampling plans to avoid the selection of adjacent units, J. Combin. Info. Syst. Sci., 18 (1993), 149-160.
|
[23] |
J. Stufken and J. H. Wright,
Polygonal designs with blocks of size $k \leq 10$, Metrika, 54 (2001), 179-184.
doi: 10.1007/s001840100137. |
[24] |
C.-L. Su, C.-Y. Tsui and A. M. Despain,
Saving power in the control path of embedded processors, IEEE Design Test of Computers, 11 (1994), 24-31.
doi: 10.1109/54.329448. |
[25] |
M. H. Tahir, I. Iqbal, M. Akhtar and J. Shabbir,
Cyclic polygonal designs with block size 3 and $\lambda = 1$ for joint distance $\alpha = 6$ to $16$, Journal of Statistical Theory and Practice, 4 (2010), 203-220.
doi: 10.1080/15598608.2010.10411981. |
[26] |
B. Victor and K. Keutzer, Bus encoding to prevent crosstalk delay, Proceedings of the 2001 IEEE/ACM International Conference on Computer-Aided Design, (2001), 57–63.
doi: 10.1109/ICCAD.2001.968598. |
[27] |
X. M. Wang, T. Feng, J. Zhang and Y. Xu,
Two-dimensional balanced sampling plans avoiding adjacent units, Discrete Mathematics, 338 (2015), 1624-1642.
doi: 10.1016/j.disc.2015.04.012. |
[28] |
J. H. Wright,
Two-dimensional balanced sampling plans excluding adjacent units, Journal of Statistical Planning and Inference, 138 (2008), 145-153.
doi: 10.1016/j.jspi.2007.05.016. |
[29] |
J. H. Wright and J. Stufken,
New balanced sampling plans excluding adjacent units, Journal of Statistical Planning and Inference, 138 (2008), 3326-3335.
doi: 10.1016/j.jspi.2006.10.020. |
[30] |
J. Zhang and Y. X. Chang,
The spectrum of cyclic BSEC with block size three, Discrete Mathematics, 305 (2005), 312-322.
doi: 10.1016/j.disc.2005.06.030. |
[31] |
J. Zhang and Y. X. Chang,
The spectrum of cyclic BSA $(v, 3, \lambda; \alpha)$ with $\alpha=2, 3$, Journal of Combinatorial Designs, 13 (2005), 313-335.
doi: 10.1002/jcd.20049. |
[32] |
J. Zhang and Y. X. Chang,
The spectrum of {BSA ($v$, 3, $\lambda$; $\alpha$)} with $\alpha$= 2, 3, Journal of Combinatorial Designs, 15 (2007), 61-76.
doi: 10.1002/jcd.20104. |
[33] |
J. Zhang and Y. X. Chang,
Existence of BSAs and cyclic BSAs of block size three, Journal of Statistical Planning and Inference, 137 (2007), 1496-1511.
doi: 10.1016/j.jspi.2006.02.009. |
[34] |
J. Zhang and Y. X. Chang,
Partitionable sets and cyclic BSECs with block size four, Journal of Statistical Planning and Inference, 139 (2009), 1974-1979.
doi: 10.1016/j.jspi.2008.09.007. |
show all references
References:
[1] |
D. Bertozzi, L. Benini and G. D. Micheli, Low power error resilient encoding for on-chip data buses, Proceedings of the Conference on Design, Automation and Test in Europe, IEEE Computer Society, (2002), 102–109.
doi: 10.1109/DATE.2002.998256. |
[2] |
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976. |
[3] |
D. Bryant, Y. X. Chang, C. A. Rodger and R. Wei,
Two-dimensional balanced sampling plans excluding contiguous units, Communications in Statistics-Theory and Methods, 31 (2002), 1441-1455.
doi: 10.1081/STA-120006078. |
[4] |
Y. M. Chee, C. J. Colbourn and A. C. H. Ling, Optimal memoryless encoding for low power off-chip data buses, 2006 IEEE/ACM International Conference on Computer Aided Design, IEEE, (2006), 369–374.
doi: 10.1145/1233501.1233575. |
[5] |
Y. M. Chee, C. J. Colbourn, A. C. H. Ling, H. Zhang and X. D. Zhang,
Optimal low-power coding for error correction and crosstalk avoidance in on-chip data buses, Des. Codes Cryptogr., 77 (2015), 479-491.
doi: 10.1007/s10623-015-0084-4. |
[6] |
C. J. Colbourn and A. C. H. Ling,
A class of partial triple systems with applications in survey sampling, Communications in Statistics-Theory and Methods, 27 (1998), 1009-1018.
doi: 10.1080/03610929808832141. |
[7] |
C. J. Colbourn and A. C. H. Ling, Balanced sampling plans with block size four excluding
contiguous units, Australasian Journal of Combinatorics, 20 (1999), 37-46.
doi: ajc.maths.uq.edu.au. |
[8] |
C. J. Duan, A. Tirumala and S. P. Khatri, Analysis and avoidance of cross-talk in on-chip buses, HOT 9 Interconnects Symposium on High Performance Interconnects, IEEE, (2001), 133–138.
doi: 10.1109/HIS.2001.946705. |
[9] |
M. Favalli and C. Metra,
Bus crosstalk fault-detection capabilities of error-detecting codes for on-line testing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7 (1999), 392-396.
doi: 10.1109/92.784100. |
[10] |
A. S. Hedayat, C. R. Rao and J. Stufken,
Sampling plans excluding contiguous units, Sampling, Handbook of Statist., North-Holland, Amsterdam, 6 (1988), 575-583.
doi: 10.1016/0378-3758(88)90070-5. |
[11] |
A. Hedayat, C. Rao and J. Stufken,
24 Designs in survey sampling avoiding contiguous units, Handbook of Statistics, 6 (1988), 575-583.
doi: 10.1016/S0169-7161(88)06026-2. |
[12] |
I. Iqbal, M. H. Tahir, M. Akhtar, S. S. A. Ghazali, J. Shabbir and N. S. Bukhari,
Generalized polygonal designs with block size 3 and $\lambda = 1$, Journal of Statistical Planning and Inference, 139 (2009), 3200-3219.
doi: 10.1016/j.jspi.2009.02.018. |
[13] |
Z. Khan, T. Arslan and A. T. Erdogan, A dual low power and crosstalk immune encoding scheme for system-on-chip buses, International Workshop on Power and Timing Modeling, Optimization and Simulation, (2004), 585–592.
doi: 10.1007/978-3-540-30205-6_60. |
[14] |
H. R. Kong, J. G. Lei and Y. Zhang,
On constructions for two dimensional balanced sampling plan excluding contiguous units with block size four, Discrete Mathematics, 308 (2008), 3729-3743.
doi: 10.1016/j.disc.2007.07.065. |
[15] |
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. |
[16] |
Y. Miao and L. Zhu,
Existence of incomplete group divisible designs, J. Comb. Math. Comb. Comput., 6 (1989), 33-49.
|
[17] |
K. N. Patel and I. L. Markov, Error-correction and crosstalk avoidance in DSM busses, Proceedings of the 2003 International Workshop on System-level Interconnect Prediction, ACM, (2003), 9–14.
doi: 10.1145/639929.639933. |
[18] |
S. Ramprasad, N. R. Shanbhag and I. N. Hajj,
A coding framework for low-power address and data busses, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7 (1999), 212-221.
doi: 10.1109/92.766748. |
[19] |
D. Rossi, V. E. S. van Dijk, R. P. Kleihorst, A. H. Nieuwland and C. Metra, Coding scheme for low energy consumption fault-tolerant bus, Proceedings of the Eighth IEEE International On-Line Testing Workshop (IOLTW), IEEE, (2002), 8–12.
doi: 10.1109/OLT.2002.1030176. |
[20] |
J. E. Simpson,
Langford sequences: Perfect and hooked, Discrete Mathematics, 44 (1983), 97-104.
doi: 10.1016/0012-365X(83)90008-0. |
[21] |
M. R. Stan and W. P. Burleson,
Bus-invert coding for low-power I/O, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 3 (1995), 49-58.
doi: 10.1109/92.365453. |
[22] |
J. Stufken,
Combinatorial and statistical aspects of sampling plans to avoid the selection of adjacent units, J. Combin. Info. Syst. Sci., 18 (1993), 149-160.
|
[23] |
J. Stufken and J. H. Wright,
Polygonal designs with blocks of size $k \leq 10$, Metrika, 54 (2001), 179-184.
doi: 10.1007/s001840100137. |
[24] |
C.-L. Su, C.-Y. Tsui and A. M. Despain,
Saving power in the control path of embedded processors, IEEE Design Test of Computers, 11 (1994), 24-31.
doi: 10.1109/54.329448. |
[25] |
M. H. Tahir, I. Iqbal, M. Akhtar and J. Shabbir,
Cyclic polygonal designs with block size 3 and $\lambda = 1$ for joint distance $\alpha = 6$ to $16$, Journal of Statistical Theory and Practice, 4 (2010), 203-220.
doi: 10.1080/15598608.2010.10411981. |
[26] |
B. Victor and K. Keutzer, Bus encoding to prevent crosstalk delay, Proceedings of the 2001 IEEE/ACM International Conference on Computer-Aided Design, (2001), 57–63.
doi: 10.1109/ICCAD.2001.968598. |
[27] |
X. M. Wang, T. Feng, J. Zhang and Y. Xu,
Two-dimensional balanced sampling plans avoiding adjacent units, Discrete Mathematics, 338 (2015), 1624-1642.
doi: 10.1016/j.disc.2015.04.012. |
[28] |
J. H. Wright,
Two-dimensional balanced sampling plans excluding adjacent units, Journal of Statistical Planning and Inference, 138 (2008), 145-153.
doi: 10.1016/j.jspi.2007.05.016. |
[29] |
J. H. Wright and J. Stufken,
New balanced sampling plans excluding adjacent units, Journal of Statistical Planning and Inference, 138 (2008), 3326-3335.
doi: 10.1016/j.jspi.2006.10.020. |
[30] |
J. Zhang and Y. X. Chang,
The spectrum of cyclic BSEC with block size three, Discrete Mathematics, 305 (2005), 312-322.
doi: 10.1016/j.disc.2005.06.030. |
[31] |
J. Zhang and Y. X. Chang,
The spectrum of cyclic BSA $(v, 3, \lambda; \alpha)$ with $\alpha=2, 3$, Journal of Combinatorial Designs, 13 (2005), 313-335.
doi: 10.1002/jcd.20049. |
[32] |
J. Zhang and Y. X. Chang,
The spectrum of {BSA ($v$, 3, $\lambda$; $\alpha$)} with $\alpha$= 2, 3, Journal of Combinatorial Designs, 15 (2007), 61-76.
doi: 10.1002/jcd.20104. |
[33] |
J. Zhang and Y. X. Chang,
Existence of BSAs and cyclic BSAs of block size three, Journal of Statistical Planning and Inference, 137 (2007), 1496-1511.
doi: 10.1016/j.jspi.2006.02.009. |
[34] |
J. Zhang and Y. X. Chang,
Partitionable sets and cyclic BSECs with block size four, Journal of Statistical Planning and Inference, 139 (2009), 1974-1979.
doi: 10.1016/j.jspi.2008.09.007. |
Type-Ⅰ | Type-Ⅱ | Type-Ⅲ | Type-Ⅳ |
Single wire undergoes transition. Adjacent wires maintain previous states | Center wire in opposite transition to an adjacent wire. The other wire in same transition as center wire | Center wire in opposite transition to an adjacent wire. The other wire maintains previous state | All three adjacent wires undergo opposite transitions |
Type-Ⅰ | Type-Ⅱ | Type-Ⅲ | Type-Ⅳ |
Single wire undergoes transition. Adjacent wires maintain previous states | Center wire in opposite transition to an adjacent wire. The other wire in same transition as center wire | Center wire in opposite transition to an adjacent wire. The other wire maintains previous state | All three adjacent wires undergo opposite transitions |
Sampling plans | Upper bounds | Leave graphs |
CPSA |
A perfect matching | |
CPSA |
A cycle of length four | |
LPSA |
see Fig. 1 | |
LPSA |
A single edge |
Sampling plans | Upper bounds | Leave graphs |
CPSA |
A perfect matching | |
CPSA |
A cycle of length four | |
LPSA |
see Fig. 1 | |
LPSA |
A single edge |
|
||||||||
|
||||||||
n=3g+t-1 | g | t | s |
72s=3(24(s-1)+18)+18 | 24(s-1)+18 | 19 | |
72s+24=3(24(s-1)+18)+42 | 24(s-1)+18 | 43 | |
72s+48=3(24s+12)+12 | 24s+12 | 13 |
n=3g+t-1 | g | t | s |
72s=3(24(s-1)+18)+18 | 24(s-1)+18 | 19 | |
72s+24=3(24(s-1)+18)+42 | 24(s-1)+18 | 43 | |
72s+48=3(24s+12)+12 | 24s+12 | 13 |
[1] |
Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020124 |
[2] |
Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020120 |
[3] |
Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044 |
[4] |
Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045 |
[5] |
Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049 |
[6] |
Lisa Hernandez Lucas. Properties of sets of Subspaces with Constant Intersection Dimension. Advances in Mathematics of Communications, 2021, 15 (1) : 191-206. doi: 10.3934/amc.2020052 |
[7] |
Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082 |
[8] |
Masaharu Taniguchi. Axisymmetric traveling fronts in balanced bistable reaction-diffusion equations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3981-3995. doi: 10.3934/dcds.2020126 |
[9] |
Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164 |
[10] |
Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350 |
[11] |
Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020118 |
[12] |
Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020129 |
[13] |
San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038 |
[14] |
Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021011 |
[15] |
Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077 |
[16] |
Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053 |
[17] |
Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065 |
[18] |
Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055 |
[19] |
Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054 |
[20] |
Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039 |
2019 Impact Factor: 0.734
Tools
Article outline
Figures and Tables
[Back to Top]