Integer single-error-correcting codes as an alternative to the internet checksum

Автор: Aleksandar Radonjić, Igor Ristić, Ivan Šćepanović

Журнал: Social Informatics Journal @socialinformaticsjournal

Статья в выпуске: 1 vol.2, 2023 года.

Бесплатный доступ

The paper considers the possibility of using integer single-error-correcting (SEC) codes instead of the Internet checksum (IC). It is shown that such a replacement can be easily carried out, since the integer SEC codes are a generalization of the IC.

Integer codes, single error correction, multimedia data, Internet checksum

Короткий адрес: https://sciup.org/170203984

IDR: 170203984 | DOI: 10.58898/sij.v2i1.41-44

Текст научной статьи Integer single-error-correcting codes as an alternative to the internet checksum

The Internet has become one of the most important means of communication. It is used not only for broadcasting television and radio programs, but also for mutual communication. The most known example is the Skype application, which allows people not only to make phone calls, but also to see their interlocutors.

Generally speaking, the Internet is a global computer network that is based on four layer networking model. The first layer is the data layer, which defines how the communication through packets delivery works between two network nodes (computer, firewall, switch or router). Above the data layer is the network layer, which deals with the routing of packets from one network node to another. The third layer is the transport layer, which is responsible for the delivery of the application data, while the last (application) layer provides an interface between the applications and the underlying network (Figure 1).

For the purpose of reliable multimedia communication, the most important layer is the transport one. At this layer, the multimedia data are delivered using User Datagram Protocol (UDP) (Aracil and Callegati, 2009). This protocol is designed for fast and simple data transmission without ensuring delivery. More precisely, by using the Internet checksum (IC), the receiver only checks whether the data was received in error. If they are received without error, the packet will be delivered to the application. Otherwise, it will be discarded, which can negatively affect the quality of multimedia content playback.

Figure 1. Encapsulation of multimedia data for transmission over the Internet.

In this paper, we will show that the problem of packet dropping can be significantly mitigated if integer single-error-correcting (SEC) codes are used instead of the IC. In addition, it is important to note the receiver would not undergo any hardware changes, since the integer SEC codes are a generalization of the IC.

Creative Commons Attribution (CC BY) license .

Radonjić, A., Ristić, I., & Šćepnović, I. (2023). Integer single-error-correcting codes as an alternative to the internet ^ checksum, Social informatics journal, 2 (1), 41-44. updates

Codes Construction

The construction principle of integer SEC codes is explained in detail in (Radonjic, 2018). Here we will list only the most important results.

Definition 1. Let = {0,1,..., 2b-2} be the ring of integers modulo 2b-1 andletBi = ^'^ an-2" be the integer representation of a b-bit byte, where an e [0, 1} and 1

is an (kb + ti, kb') integer code, where c = (Ci, C2,..., Ct, 1) e ^V_A /s the coefficient vector and Вы ^G A^

is an integer.'

Definition 2. Letx- (Bi, B2,..., Bk, Bm) e Z^ ,y = (Bi, &,..., Bk, Вы) e Z^ ande = (B1-B1, B2-

B2,...,Bk-Bk, Вы-Вы) = (ei, 62,..., ek, еы) ^G ^‘-i be the sent codeword, the received codeword and the error vector respectively. Then, the syndrome S of the received codeword is defined as

S^Q'B-B^ (mod24-l) = f e^ (mod^-t)

7=17=1

Definition 3. The set of syndromes corresponding to single errors is defined as

Theorem 1. The codes defined by (2) can correct all single errors if there exists к different coefficients

С, E Z^X [0,1} SUCh f/iaf J €_{b k} | = 2 • b • (k + 1), where I С,к I denotes the cardinality of Чь.к ■

Proof. The theorem is proved in (Radonjic, 2018).

In order for the data to be correctly encoded/decoded, it is necessary (with the help of a computer) to find the coefficients Ci. For the purposes of this paper, we are interested only in the values of the Ci’s when b = 16. Out of a total of 2031 found coefficients, Table 1 shows 690 of them.

Comparison with the Internet Checksum

The IC, in essence, is a special case of 16-bit integer SEC codes. This can be seen from the fact that it can be defined as

IC(k) = L e Z^_X;^в^ Ви (mod 216 -1) I

I 7=1J where x = (Bi, B2,..., Bk, Bm) e Z^f^ and к > 1. On the other hand, the 16-bit integer SEC codes are defined as

I 7=1J where x= (Bi, B2,..., Bk, Bk^eZ^, c = (Ci, C2,..., Ck, A^Z^ and 1 < k< 690 (Table 1).

Although the construction differences between the mentioned algorithms are minimal, they have a great.

Table 1. First 690 coefficients for 16-bit integer SEC codes.

3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33
35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65
67	69	71	73	75	77	79	81	83	85	87	89	91	93	95	97
99	101	103	105	107	109	111	113	115	117	119	121	123	125	127	129
131	133	135	137	139	141	143	145	147	149	151	153	155	157	159	161
163	165	167	169	171	173	175	177	179	181	183	185	187	189	191	193
195	197	199	201	203	205	207	209	211	213	215	217	219	221	223	225
227	229	231	233	235	237	239	241	243	245	247	249	251	253	259	261
263	265	267	269	271	273	275	277	279	281	283	285	287	289	291	293
295	297	299	301	303	305	307	309	311	313	315	317	319	321	323	325
327	329	331	333	335	337	339	341	343	345	347	349	351	353	355	357
359	361	363	365	367	369	371	373	375	377	379	381	383	385	387	389
391	393	395	397	399	401	403	405	407	409	411	413	415	417	419	421
423	425	427	429	431	433	435	437	439	441	443	445	447	449	451	453
455	457	459	461	463	465	467	469	471	473	475	477	479	481	483	485
487	489	491	493	495	497	499	501	503	505	507	517	519	521	523	525
527	529	531	533	535	537	539	541	543	545	547	549	551	553	555	557
559	561	563	565	567	569	571	573	575	577	579	581	583	585	587	589
591	593	595	597	599	601	603	605	607	609	611	613	615	617	619	621
623	625	627	629	631	633	635	637	643	645	647	649	651	653	655	657
659	661	663	665	667	669	671	673	675	677	679	681	683	685	687	689
691	693	695	697	699	701	703	705	707	709	711	713	715	717	719	721
723	725	727	729	731	733	735	737	739	741	743	745	747	749	751	753
755	757	759	761	763	773	775	777	779	781	783	785	787	789	791	793
795	797	799	801	803	805	807	809	811	813	815	817	819	821	823	825
827	829	831	833	835	837	839	841	843	845	847	849	851	853	855	857
859	861	863	865	867	869	871	873	875	877	881	883	885	887	889	891
893	899	901	903	905	907	909	911	913	915	917	919	921	923	925	927
929	931	933	935	937	939	941	943	945	947	949	951	953	955	957	959
961	963	965	967	969	971	973	975	977	979	981	983	985	987	989	991
993	995	997	999	1001	1003	1005	1007	1041	1043	1045	1047	1049	1051	1053	1055
1057	1059	1061	1063	1065	1067	1069	1071	1073	1075	1077	1079	1081	1083	1085	1091
1093	1095	1097	1099	1101	1103	1105	1107	1109	1111	1113	1115	1117	1119	1121	1123
1125	1127	1129	1131	1133	1135	1137	1139	1141	1143	1145	1147	1149	1155	1157	1159
1161	1163	1165	1167	1169	1171	1173	1175	1177	1179	1181	1183	1185	1187	1189	1191
1193	1195	1197	1199	1201	1203	1205	1207	1209	1211	1213	1219	1221	1223	1225	1227
1229	1231	1235	1237	1239	1241	1243	1245	1247	1249	1251	1253	1255	1257	1259	1261
1263	1265	1267	1269	1271	1273	1287	1289	1291	1293	1295	1297	1299	1301	1303	1305
1307	1309	1311	1313	1315	1317	1319	1321	1323	1325	1327	1329	1331	1333	1335	1337
1339	1341	1347	1349	1351	1353	1355	1357	1359	1361	1363	1365	1367	1369	1371	1371
1375	1377	1379	1381	1383	1385	1387	1389	1391	1393	1395	1397	1399	1401	1403	1405
1411	1413	1415	1417	1419	1421	1423	1425	1427	1429	1431	1433	1435	1437	1439	1441
1443	1445	1447	1449	1451	1453	1455	1457	1459	1461	1463	1465	1467	1469	1475	1477
1479	1481

Although the construction differences between the mentioned algorithms are minimal, they have a great impact on their performance: the IC can detect burst errors of length up to 15 bits, while 16-bit integer SEC codes can correct all single errors within an N-bit codeword (N ≤ 32512). In other words, if error control were to be performed using the IC, the receiver would discard all corrupted packets, which could degrade the quality of service perceived by the user. However, if error control were to be performed using integer SEC codes, the receiver could repair the vast majority of the corrupted packets, especially if they are transmitted over optical links [according to (Stone and Partridge, 2000; James, 2005; Yao et al. 2016), 90% of all channel errors are single errors].

Apart from this, it should be noted that using 16-bit integer SEC codes (instead of the IC) has no negative effect on the packet size. From (Aracil and Callegati, 2009) we know that the packet size depends on the version of the Internet protocol (IP) used. In particular, if voice data (VoIP packets) are delivered over IP version 4 (IPv4) network, the IC protects between 60 and 280 bytes (Figure 2). On the other hand, if the transmission is carried out over IP version 6 (IPv6) network, the IC will protect 84 to 304 bytes. As for delivering television content (IPTV packets), the IC covers at least 228 bytes in the case of transmission over an IPv4 network, i.e. at least 252 bytes if an IPv6 network is used. All these facts point to the conclusion that 16-bit integer SEC codes can protect all multimedia packets.

Figure 2. The packet fields covered by the IC

However, for the integer SEC decoder to be able to correct single errors, it is necessary to reserve | £J х 12 • 6 3Vog₂ fk +111 £ 1221121 х 132 hJo_& f69 ^^ ^ ≤ ≈ 0.116 MB of memory (for storing the syndrome table). This, of course, is not a problem for today’s processors that have several MB of the cache (Table 2).

Conclusions

The transmission of multimedia data over the Internet suffers from the problem of dropping corrupted packets. The reason for this lies in the inability of the IC to correct channel errors. In this paper, we have presented one solution that can improve the transmission of multimedia data over the Internet. The proposed solution is based on replacing the IC with integer codes that can correct single errors.

Conflict of interests

The authors declare no conflict of interest.

Список литературы Integer single-error-correcting codes as an alternative to the internet checksum

Aracil, J., and Callegati, F. 2009. Enabling optical internet with advanced network technologies. Springer-Verlag.
Dravida, S., and Damodaram, R. 1991. “Error detection and correction options for data services in B-ISDN.” IEEE Journal on Selected Areas in Communications, 9(9), 1484-1495. doi.org/10.1109/49.108685
James, L. B. 2005. Error behaviour in optical networks. doi:10.17863/CAM.11801.
Radonjic, A. 2018. (Perfect) integer codes correcting single errors. IEEE Communications Letters 22 (1):17-20. doi:10.1109/lcomm.2017.2757465.
Stone, J., and Partridge, C. 2000. “When the CRC and TCP checksum disagree.” Computer Communication Review 30 (4): 309-319. doi:10.1145/347057.347561.
Yao, S., Liu, X., and Liu, D. 2016. “The impact of differential pre-coding on 25-Gbit/s EDB, NRZ and NRZ-NFC.” IEEE 802.3ca Task Force.

Статья научная