LABORATORY 3

Laboratory of Data Analysis, Error Correction Codes

and Cryptology

Head of Laboratory – Dr.Sci. (Techn.), Prof. Victor Zyablov

Tel.: (095) 299-50-96; E-mail: zyablov@iitp.ru

The leading researchers of the laboratory include:

Dr.Sci.(Math.)

V. Sorokin

Dr.

E. Petrova

Dr.

V. Aphanasiev

Dr.

S. Pirogov

Dr.

A. Barg

Dr.

V. Sidorenko

Dr.

S. Bezrucov

Dr.

I. Stenina

Dr.

A. Davydov

Dr.

A. Trushkin

Dr.

A. Genkin

Dr.

D. Zigangirov

Dr.

V. Gitis

 

A. Chmora

Dr.

E. Jurkov

 

A. Vainshtok

Dr.

V. Pereverzev-Orlov

 

E. Vashenko

Directions of activity:

MAIN RESULTS

Error Control Codes and Information Transmission

The following problems are under consideration:

The investigation of general properties of rectangular codes was continued. (The class of rectangular codes includes all linear, group, and many nongroup codes). For the class of rectangular codes there exists a well defined minimal trellis representation that meets the requirements of symbolwise a posteriori probability (APP) decoding algorithms. A modified trellis representation was proposed with multiple final states (splitted trellis) that is suited for simultaneous decoding of several cosets using a forward/backward type APP decoder. We give conditions for the minimality of splitted trellises. An application for our decoding algorithm is improved multistage decoding of multilevel codes.

Investigations of woven convolutional codes were continued. The error exponents and decoding complexity of binary woven codes with outer and inner warp are studied. It is shown that for both constructions an error probability that is exponentially decreasing with the memory of woven codes can be achieved with a non-exponentially increasing decoding complexity. Furthermore, the error exponent for woven convolutional codes with inner warp is larger than the one for woven convolutional codes with outer warp. The asymptotic lower bounds on the active distances of the woven convolutional codes are obtained and it is shown that these distances can be bounded from below by linearly growing functions with a strictly positive slope for all rates of the concatenated codes.

Properties of pulse position hopped CDMA systems for Impulse Radio Multiple Access implementation were investigated. Due to the theoretical results the number of users may be ten times greater than in systems with conventional approaches.

The program on bounding invariants of codes initiated in 1997 was to some extent completed this year. In particular, the scope of the polynomial method of coding theory was extended to bounds on the distance distribution. A number of new asymptotic bounds for both codes and designs in the Hamming and Johnson spaces were found. These results are of universal nature, that is they enable one to derive bounds on any linear forms of the distance distribution of a code. An application of this technique was demonstrated in new asymptotic estimates on the covering radius of linear codes.

In joint works was proved the existence of codes with identifying parent property for arbitrary number t of parents (Previously this was only known for t=2), the volume of the sphere was computed in some submanifolds of the Grassmann manifold G(k,n) over R and C, and this result was applied to derive sphere-packing bounds on codes in G(k,n), a family of linear-time decodable binary codes was constructed with exponentially falling error probability for all the rates less than the channel capacity.

The theory of saturating sets in the projective geometry is developed. A new concept of saturating density is introduced and a number of new infinite families of covering codes with the best known parameters are obtained.

Infinite sequences of extensions of Galois fields with arbitrary basis are constructed. It gives iterated presentations for infinite towers of extended fields with almost linear asymptotic complexity of arithmetic.

A secure and versatile cryptographic protocol for biometric data authentication has been developed. This protocol supports realistic scenarios for biometric data authentication which provides the scalability and flexibility required by the biometric data authentication over the Internet, and by the diversity of scenarios that are part of it. Accommodating this variety of scenarios and requirements, both in terms of performance and security, into a simple and compact protocol is the main challenge and accomplishment of the protocol. This protocol is intended to provide authenticated biometric (not only) data transfer for the developed IP-layer protocols, as well as a key management solution for other security applications over the Internet.

During 2000 laboratory was cooperated with universities of Germany, Sweden and Italy. The main topics of the cooperation were continuation of many years investigations in communication problems and combinatorial problems in vector spaces. With Ulm University (Germany) the problems of coded modulation, capacity and problems of rectangular codes theory were considered. The work was supported by Deutsche Forschungs Gemeinschaft.

 

Concatenated constructions based on conventional convolutional codes were investigated with University of Lund (Sweden). These investigations was supported by Royal Academy of Sweden.

Covering codes over arbitrary finite fields and their connection with saturating sets in projective geometry were considered with Departments of Mathematics of Perugia University, Italy.

Some members of the laboratory are involved in joint research with the Research Center of the Bell Labs (USA).

The other works were supported by Grant RFFI No. 99-01-00840 and By the Research Contract with LoNIIS (St.-Petersburg Branch of Scientific Research Institute of Communications) "Development of principles of using machine systems of speech recognition, technological means for their realization, and creation of pilot areas for experimental verification of accepted solutions".

Geoinformation Technologies and Systems

Important theoretical and applied results on the field of geoinformaion technologies were developed. Special attention is given to the network aspects of geoinformaton technologies and geographic information systems (GIS) applied to the analysis and prediction of social and natural processes and phenomena.

Analytical GISs process geographical information (GI) presented digital model form. GI models are determined by 3 main concepts: GI entities, GI attributes and GI relations.

There are four types of GI entities:

  1. Geographical objects, e.g., administrative units, deposits, seismic sources.

  2. Geographical phenomena: e.g., social and natural events or catastrophes.

  3. Geographical processes: e.g., social, economy, natural, and man-made processes.

  4. A set of points attached to regular or irregular grid: e.g., representation of geophysical fields, representation of a set of survey points.

The attributes represent the concepts, which describe the entities. There are many ways for attribute classification. Three types of attributes are the most important from analytical GIS point of view: principle properties of the GI entities, spatial properties and temporal properties.

The relations represent the concepts, which describe ratios within entities, within attributes and between entities and attributes.

The following problems, which are solved by analytical GISs are following from this consideration:

  1. Estimation, extraction and understanding the relationships within/between the principal, spatial and temporal attributes of entities.

  2. Detection, recognition and understanding the relationships within/between the geographical objects, phenomena, processes and sets of points.

  3. Inference, extrapolation, and forecasting the goal and preliminary unknown attributes of entities.

  4. Prediction, recognition and understanding the goal and preliminary unknown of entities.

The fundamental principles of geoinformation technology for extraction from GI essential information and knowledge and for using the knowledge for forecasting the unknown relationships and for detecting the unknown geographical phenomena and objects are under development. Some of the elements of the technology have been realized in WWW analytical GISs GeoProcessor and COMPASS.

WWW analitical GIS GeoProcessor (http://www.iitp.ru/projects/geo, http://borneo.

gmd.de/and/geoprocessor

) is intended for publications and complex analysis of spatio-temporal characteristics of geological environment and for deciding forecasting and zonation problems in Earth sciences (natural hazard assessment, mineral and oil/gas deposits exploration). The system supports remote access to geographical information, interactive cartographic analysis of raster, vector and point data, spatial data mining and plausible inference. The system helps to evaluate the environment properties on the base of principle of analogy using the methods of plausible reasoning of forecast maps on a complex of raster maps: method of similarity on a precedent set, method of similarity on expert fuzzy logic knowledge, method of membership function for two classes, method of nonparametric regression, the method of certainty function for classification on monotone feature space. GeoProcessor is realized as Java applet in client-server architecture.

Within the framework of the project "ASPELEA" of EC Inco-Copernicus program the system GeoProcessor was used for data processing and WWW application designing for three seismic activity regions (http://www.iitp.ru/projects/geo). Linear geological and geophysical data were processed and the feature raster fields were generated, relationship between feature fields and spatially distributed seismic events were investigated, also spatio-temporal distribution of the earthquakes epicenters was investigated. The users can produce online their own experiments on represented data.

A new version of the WWW analytical GIS COMPASS II (Cartography Online Modeling, Presentation and Analysis System) realized as Java applet in client-server architecture was designed (http://gis.iitp.ru/). Friendly and interactive interface for multilayer vector GI cartographic representation and intuitive understandable tools for spatio-temporal data mining based on interactive analysis of complex properties of geographical objects make the system available for wide range of the Internet users (non-professionals and specialists). WWW applications were implemented on the base of COMPASS: Russia demographic indices http://gis.iitp.ru/undp, Marketing information system http://gis.iitp.ru/siemens. The users can produce online their own experiments on represented data.

International cooperation, conferences, exhibitions. Scientific cooperation within the framework of ASPELEA project of the INCO-COPERNICUS program, and on the base of bilateral agreements with Germany Center on Information Technologies (GMD, Germany), the Laboratory of Applied Logic (Hungary), the Institute of Rock Structure and Mechanics (IRSM), Academy of Sciences of the Czech Republic, and National Geophysical Research Institute of India are carried out.

The research results were reported on the conferences and workshops in Germany, Austria, and Russia. The systems GeoProcessor and Compass were presented with the support of RF Ministry of sciences at international exhibitions on information technologies CeBit (Germany) and Simo’2000 (Spain).

GRANTS FROM:

Partner System Group

The methods and tools for decision support systems in medicine were studied. New methods for processing of multidimensional input data, supporting of different users interaction, integration of knowledge and data from different sources were proposed. The problems of conceptual modeling for time processes were investigated.

Development of the new system for data and knowledge processing based on the methods created earlier is in progress. The system unites interactive procedures of expert knowledge acquisition, analysis of empirical data and knowledge base enlargement.

Pattern recognition methods with the using of threshold network have been effectively applied in the tasks of continuous parameter prediction, forecasting in dynamic environment, image processing and interpretation.

GRANTS FROM:

THEORY OF THE SPEECH SIGNAL

There were studied the methods of solving for dynamic inverse problem with respect to controls of articulators when input signals were articulatory movements measured by X-ray microbeam system and cinemaradiography. Quasi-potential and quasi-kinetic energy used as criteria of optimality provided the accuracy of approximation of articulatory movements within the accuracy of measurements. The effects of controls reorganization for different rates of articulation and compensation of bite-block were reproduced. Obtained results are strong arguments in the benefit of the hypothesis of internal model in articulatory control system, and they point out to possible mechanisms of the internal model. The estimation of the maximal bit rate for an articulatory vocoder was obtained. The study of acoustic and articulatory detectors was continued. Experimental assessment of self-descriptiveness of acoustic detectors and separability of articulatory detectors was carried out. Preliminary tests of sequential decoding for the task of digits recognition were conducted. 90% segmentation of the data-base of spoken digits for 48 speakers, 2 types of telephone-set and 3 types of microphones was accomplished.

Publications in 2000

  1. Sidorenko V., Maucher J., Bossert M., and Lucas R. Rectangular Codes in Ite-rative Decoding. Proc. of 3rd ITG Conference Source and Channel Coding, Muenchen, Jan. 2000, p. 215-218.

  2. Sidorenko V., Maucher J., Bossert M. Bases of rectangular codes, Proc. of 2000 IEEE Intern. Symp. on Inf. Theory, Sorrento, Italy, June, 2000, p. 30.

  3. Sidorenko V., Maucher J., Bossert M., and Lucas R. Rectangular Codes in Iterative Decoding. Submitted to IEEE Trans.on Communications.

  4. Griesser H., Sidorenko V., Bossert M. A Trellis Based Algorithm for APP Decoding of Cosets, submitted to ISIT 2001.

  5. Ashikhmin A., Barg A., and Litsyn S. Estimates of the distance distribution of codes and designs, preprint (February 2000), IEEE Trans. Inform. Theory, to appear.

  6. Barg A., Justesen J., Thommesen C. Concatenated codes with fixed inner code and outer code randomly selected, preprint (February 2000), IEEE Trans. Inform. Theory, to appear.

  7. Barg A. and Jaffe D. Numerical results on the asymptotic rate of linary codes, "Codes and Association Schemes," AMS (2000), p.25-32.

  8. Barg A. and Nogin D. Bounds on packings of spheres in the Grassmann manifolds, DIMACS report 2000-19 (http://dimacs/rutgers.edu), submitted for publication.

  9. Ashikhmin A., Barg A., and Litsyn S. Estimates of the distance distribution of nonbinary codes, with applications."Codes and Association Schemes," AMS (2000), p. 287-302.

  10. Ashikhmin A., Barg A., and Litsyn S. A new upper bound on the reliability function of the Gaussian channel,IEEE Trans. Inform. Theory, 46. Also Proc. ISIT-2000, Sorrento.

  11. Ashikhmin A., Barg A., Knill E., and Litsyn S. Quantum error detection, IEEE Trans. Inform. Theory, vol 46, May 2000, Part I: Statement of the problem, p. 778-789, Part II: Bounds, p. 790-801. Also Proc. ISIT-2000, Sorrento.

  12. Barg A. and Kabatiansky G. Codes with the identifiable parent property: the case of mulitple parents, Proc. ACCT-7, Bansko, Bulgaria, June 2000, p. 68-71.

  13. Barg A., Cohen G., Encheva S., Kabatiansky G., and Zemor G. A hypergraph approach to the identifying parent property: the case of multiple parents, DIMACS Report 2000-20 (http://dimacs/rutgers.edu), submitted for publication.

  14. Barg A., On polynomial invariants of codes, matroids and the partition function, Proc. ISIT 2000, Sorrento.

  15. Barg A. and Zemor G. Linear-time decodable, capacity achieving binary codes with exponentially falling error probability (September 2000), submitted for publication.

  16. Ashikhmin A. and Barg A. Bounds on the covering radius of linear codes, preprint (December 2000), submitted for publication.

  17. Barg A. and Litsyn S. Editors, "Codes and Association Schemes," American Mathematical Society, Providence, RI, 2000.

  18. Davydov A.A. and Ostergard P.R.J. "New quaternary linear codes with covering radius 2," Finite Fields and their Applications, vol. 6, 2000, p. 164-174.

  19. Davydov A.A.and Ostergard P.R.J. "On saturating sets in small projective geometries", Europian Journal of Combinatorics, vol. 21, 2000, p. 563-570.

  20. Davydov A.A. and Ostergard P.R.J. "Linear codes with covering radius R=2,3 and codimension tR", IEEE Transactions on Information Theory, to appear.

  21. Wintzell Ola, Zigangirov D.K., Zigangirov K.Sh. "On the capacity of a pulse position hopped CDMA system" IEEE Int Symp Inf.Theory (ISIT'2000), p. 135, Sorento, Italy, 25-30 June, 2000.

  22. Wintzell Ola, Zigangirov D.K., Zigangirov K.Sh. "On the capacity of a pulse position hopped CDMA system", Submitted for publication in IEEE Trans. on Information Theory.

  23. Трушкин А.В. О сравнительной сложности алгоритмов построения синдромной решетки линейного блокового кода // Пробл. передачи информ. 2000. Т. 36. № 2. С. 10-18.

  24. Чмора А.Л. Схема одноразовых паролей с квитированием // Технический отчет. BioLink Technologies International, Inc., Октябрь 1999.

  25. Чмора А.Л. Схема одноразовых паролей с квитированием. Версия 1.1 // Технический отчет. BioLink Technologies International, Inc., Ноябрь 1999.

  26. Чмора А.Л. Схема одноразовых паролей с квитированием. Версия 1.2 // Технический отчет. BioLink Technologies International, Inc., Декабрь 1999.

  27. Чмора А.Л. BDAP версия 1.4. Спецификация // BioLink Technologies International, Inc., 2000.

  28. Andrew Chmora. Versatile Cryptographic Protocol for Biometric Data Authentication. Submitted to Eurocrypt 2001. November, 2000.

  29. Afanassiev V.B. and Davydov A.A. Finite Field Towers: Iterated Presentation and Complexity of Arithmetics // Submitted to Finite Fields and their Applications.

  30. Nielsen J., Afanassiev V., Bach-Andersen J. A Dynamic Model of the Indoor Channel, accepted in Wireless Personal Commnications.

  31. Bezrukov S.L., Piotrowski V.P. Shadows and isoperimetry in bipartite graphs // presented by V.P. Piotrowski at SIAM conf. on Discr. Math., Minneapolis, June 2000.

  32. Bezrukov S.L., Serra O. A local-global principle for vertex-isoperimetric problems // presented by O. Serra at the International Slovenian Conference on Graph Theory in 2000 and at a seminar in the Mathematical Institute of the Hungarian Acad. Sci, September 2000, to appear in Discr. Math.

  33. Bezrukov S.L., Elsaesser R., Monien B., Preis R., Tillich J.-P. New spectral lower bounds for the bisection width of graphs // presented by R. Preis at the International Conference "`Graph-Theoretic Aspects of Computer Science'' (WG2000), Germany, July 2000.

  34. Bezrukov S.L., Elsaesser R. Edge-Isoperimetric Problems for Powers of Regular Graphs // presented by R. Elsaesser at the International Conference ODAS-2000, Rostock, Germany, September 2000.

  35. Bezrukov S.L., Das S., Elsaesser R. An edge isoperimetric problem for powers of the Petersen graph // Annals of Combinatorics, vol. 4, 2000, 153-169.

  36. Bezrukov S.L., Elsaesser R. The spider poset is Macaulay // J. Comb. Theory, vol. A-90, 2000, 1-26.

  37. Bezrukov S.L., Leck U. Some new results on Macaulay posets. In: Numbers, Information and Complexity, I. Althoefer, N. Cai, G. Dueck, L.Khachatrian, M. Pinsker, A. Sarkozy, I. Wegener and Z. Zhang (eds.), Kluwer Academic Publishers, 2000, 75-94.

  38. Bezrukov S.L., Chavez J.D., Harper L.H., Roettger M. U.-P. Schroeder, The congestion of n-cube layout on a rectangular grid // Discr. Math., vol. 213, 2000, 13-19.

  39. Bezrukov S.L., Serra O. A local-global principle for vertex-isoperimetric problems // to appear in Discr. Math.

  40. Bezrukov S.L. Discrete extremal problems // Big Russian Encyclopedia (in Russian)

  41. Bezrukov S.L. Embedding complete trees into the hypercube // to appear in Discr. Appl. Math.

  42. Amendola A., Bayer J., Ermoliev Y., Ermoliev T., Gitis V., Koff G. A System Approach to Modeling Catastrophic Risk and Insurability. "Natural hazards", 21, Netherlands, Kluver Academic Publishers, 2000, 381-393.

  43. Гитис В.Г., Вайншток А.П., Довгялло А.В. Сетевые геоинформационные технологии и системы. – Труды VII Всероссийского форума "Геоинформационные технологии. Управление. Природопользование. Бизнес. Образование". М.: РАГС, 2000, 91-97.

  44. Gitis V. An approach to WWW On-line intelligent geo-reference information analysis. – Abstr. of 2nd Euroconference Risk Global and Catastrophe Risk Management Earthquake Risk in Europe, IIASA, Luxemburg, Austria, 2000, 13.

  45. Gitis V., Osher B., Dovgiallo A., Vainshtok A. COMPASS: Cartography On-line Modeling, Presentation and Analysis System. – Proc. of the 5th EC-GIS Workshop, Stresa, Italy, EC JRC, 2000, 487-497.

  46. Gitis V., Vainchtok A. Final Report on project Assessment of Seismic Potential in European Large Earthquake Areas “ASPELEA”, EC Project INCO-COPERNICUS, 2000, 10 p.

  47. Гитис В.Г., Вайншток А.П., Довгялло А.В., Ошер Б. Сетевые аналитические геоинформационные технологии и системы. – Труды VII национальной конференции по искусственному интеллекту (КИИ'2000), Переславль-Залес-ский, 2000, 741-749.

  48. Юрков Е.Ф. Система анализа характеристик акустического процесса при разрушении образцов горных пород // Вулканология и сейсмология (в печати).

  49. Belikova T.P., Stenina I.I., Yashunskaya N.I. Computer-Aided Methods to Support Image Interpretation in the Case of Uncertainty. In: Procеed. of 14 Int. Congress on Assisted Radiology and Surgery – CARS’ 2000, San-Francisco (USA): Excerpta Medica, Intern. Congess Series V. 1214, p. 1050.

  50. Belikova T.P., Stenina I.I., Yashunskaya N.I. Computer-aided methods to recover strategies for visual search and navigation // SPIE Congress on Medical Imaging. Medical Imaging 2000. San-Diego, USA, Proced. SPIE V. 3981, 2000, p. 240-250.

  51. Vitushko M., Gurov N., Pereverzev-Orlov V. "Syndrom" as a method of conceptual modeling // Pattern Recognition and Image Analysis (to print).

  52. Sorokin V.N., Leonov A.S., Trushkin A.V. Estimation of stability and accuracy of inverse prbolem solution for the vocal tract // Speech Communication. 2000. V. 30. No. 1. P. 55-74.

  53. Leonov A.S., Sorokin V.N. Inverse problem for the vocal tract: Identification of control forces from articulatory movements // Pattern Recognition and Image Analysis. 2000, No. 10. P. 110-126.

  54. Leonov A.S., Sorokin V.N. Inversion from articulatory movements to control forces // Proc. 5th Seminar on Speech production, Kloster Seeon, 2000, P. 17-20.

  55. Сорокин В.Н. Концепция внутренней модели в речеобразовании и восприятии речи. – Труды 10 сессии Российского акустического общества. 2000, т. 2, с. 248-256.

  56. Леонов А.С., Сорокин В.Н. Обратная задача для управления артикуляцией // Доклады Академии Наук. 2000. Т. 374. № 6.